剑指 Offer 54. 二叉搜索树的第k大节点
本问题对应的 leetcode 原文链接：剑指 Offer 54. 二叉搜索树的第k大节点
本题对应打卡问题：【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点
问题描述
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例1 :
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2：
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
限制:
- 1 ≤ k ≤ 二叉搜索树元素个数
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
int k = 0;
int target = 0;
public int kthLargest(TreeNode root, int k) {
// 中序遍历：有序的序列 左 根 右 从小到大排序的
// 右 根 左 从大到小的排序
this.k = k;
right_root_left(root);
return target;
}
void right_root_left(TreeNode root){
if(root == null || k <= 0) return;
right_root_left(root.right);
// 打印当前根节点
k--;
if(k == 0){
target = root.val;
}
right_root_left(root.left);
}
}
时间复杂度：最差为 O(n)，平均为 logn
空间复杂度：最差为 O(n)，平均为 logn