概述
题目：给定一棵二叉搜索树，请找出其中第k大的节点
方法：递归右中左遍历
用一个全局变量 k 来维护函数的参数 k ，递归右中左遍历
- 时间复杂度 O(n)
- 空间复杂度 O(n)，递归栈的深度
class Solution {
int k, res;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
void dfs(TreeNode root) {
if (root == null) {
return ;
}
dfs(root.right);
if (k == 0) {
return ;
}
if (--k == 0) {
res = root.val;
}
dfs(root.left);
}
}
最后
以上就是繁荣酸奶为你收集整理的面试题54：二叉搜索树的第k大节点的全部内容，希望文章能够帮你解决面试题54：二叉搜索树的第k大节点所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![区间（树上）第k小（大）问题P3834 【模板】可持久化线段树 1（主席树） 静态区间第k小。P2633 Count on a tree 静态树上路径第k小。P3380 【模板】二逼平衡树（树套树）P4175 [CTSC2008]网络管理P3302 [SDOI2013]森林 支持动态合并的树上路径第k小。（肯定在线啊。](/uploads/reation/bcimg13.png)
![[spoj COT - Count on a tree]树上第K小[spoj COT - Count on a tree]树上第K小](/uploads/reation/bcimg14.png)
发表评论 取消回复