力扣|力扣 - 剑指 Offer 54. 二叉搜索树的第k大节点
题目
【力扣|力扣 - 剑指 Offer 54. 二叉搜索树的第k大节点】剑指 Offer 54. 二叉搜索树的第k大节点
思路1
- 二叉搜索树的特性就是中序遍历结果为递增序列,而题目要求的是第 k 大节点,所以就应该是要遍历结果为降序,
- 按照
先遍历左子树、输出节点、遍历右子树
得到的是升序结果,要得到降序,需要按照先遍历右子树、输出节点、再遍历左子树
即可 - 什么时候结束递归呢?有两种情况:
- root 为
null
的时候,代表遍历到叶子节点了,此时需要返回 - 当前节点为第 k 大节点:每遍历到一个节点,将 k 值减1,直到 k 值为 0 ,说明找到第 k 大节点了,此时记录下节点的值,然后开始返回
- root 为
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)\)
推荐阅读
- 剑指|剑指 Offer 13. 机器人的运动范围(dfs,bfs)
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- 剑指offer60.n个骰子的点数
- 剑指offer——最小的K个数
- Android|年后备战金三银四(Android面试吃透这一篇就没有拿不到的offer......)
- 剑指黄昏
- 剑指offer15.二进制中1的个数
- java|阿里工作8年,肝到P8就剩这份学习笔记了,已助朋友拿到10个Offer
- 字节前端面试经验(已拿到offer)