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

Lin2J
2021-07-21 / 0 评论 / 144 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$:最差情况下,树退化成链表,需要存储所有的节点。