正文
力扣 - 剑指 Offer 54. 二叉搜索树的第k大节点
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
题目
剑指 Offer 54. 二叉搜索树的第k大节点
思路1
-
二叉搜索树的特性就是中序遍历结果为递增序列,而题目要求的是第 k 大节点,所以就应该是要遍历结果为降序,
-
按照
先遍历左子树、输出节点、遍历右子树
得到的是升序结果,要得到降序,需要按照
先遍历右子树、输出节点、再遍历左子树
即可
-
什么时候结束递归呢?有两种情况:
-
root 为
null
的时候,代表遍历到叶子节点了,此时需要返回
-
当前节点为第 k 大节点:每遍历到一个节点,将 k 值减1,直到 k 值为 0 ,说明找到第 k 大节点了,此时记录下节点的值,然后开始返回
代码
class Solution {
int k;
int res;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
public void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.right);
k--;
if (k == 0) {
res = node.val;
return;
}
dfs(node.left);
}
}
复杂度分析
-
时间复杂度:\(O(N)\)
-
空间复杂度:\(O(N)\)
先遍历左子树、输出节点、遍历右子树
得到的是升序结果,要得到降序,需要按照
先遍历右子树、输出节点、再遍历左子树
即可
-
root 为
null
的时候,代表遍历到叶子节点了,此时需要返回 - 当前节点为第 k 大节点:每遍历到一个节点,将 k 值减1,直到 k 值为 0 ,说明找到第 k 大节点了,此时记录下节点的值,然后开始返回
class Solution {
int k;
int res;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
public void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.right);
k--;
if (k == 0) {
res = node.val;
return;
}
dfs(node.left);
}
}