二叉搜索树 - LeetCode 54.二叉搜索树的第k大节点

给定一棵二叉搜索树，找出其第 k 大的节点的值。(1≤k≤N ，N为二叉搜索树节点个数)

image.png

• 我们知道：二叉搜索树的中序遍历为递增序列，所以二叉搜索树的中序遍历倒序为递减序列。
• 因此，求 二叉搜索树第k大的节点 可转化为求 此树的中序遍历倒序的第k个节点

class Solution {
    int res, k;
    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(this.k == 0) return;
        if(--this.k == 0) res = root.val;
        dfs(root.left);
    }
}

• 时间复杂度 O(N) ： 当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为N ，占用 O(N) 时间。
• 空间复杂度 O(N) ： 当树退化为链表时（全部为右子节点），系统使用 O(N) 大小的栈空间。

image.png

✅ 230. 二叉搜索树中第 K 小的元素

image.png

class Solution {
    int res, k;
        public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (k == 0) return;
        if (--k == 0) res = root.val;
        dfs(root.right);
    }
}