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

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

解题思路：

基于二叉搜索树的特点，可以对二叉搜索树进行中序遍历，然后将第 $k$ 个节点的值返回即可。

代码：

public int kthLargest(TreeNode root, int k) {
    Deque<TreeNode> queue = new LinkedList<>();
    if (root != null) {
        queue.push(root);
    }
    int ans = 0;
    while (root != null || !queue.isEmpty()) {
        while (root != null) {
            queue.push(root);
            root = root.right;
        }
        root = queue.pop();
        if (--k == 0) {
            ans = root.val;
            break;
        }
        root = root.left;
    }
    return ans;
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 是二叉搜索树的节点数。最差情况下，$k = N$，需要遍历所有的节点。
• 空间复杂度$O(N)$：最差情况下，树退化成链表，需要存储所有的节点。