侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

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

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 181 阅读 / 477 字 / 正在检测是否收录...

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

评论区