二叉搜索树的第k大节点

解题思路：dfs+逆中序

  1. 按照右->根->左的顺序（中序遍历倒序）遍历二叉树；

  2. 当结果数组长度大于 k 停止递归，提前返回；

复杂度：

  1. 时间复杂度：O(N)，当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 N；

  2. 空间复杂度：O(N)，当树退化为链表时（全部为右子节点），系统使用 O(N) 大小的栈空间；

代码实现：

function kthLargest(root: TreeNode | null, k: number): number {
    function dfs(root: TreeNode) {
        if (root === null) return;
        if (k < res.length) return;

        dfs(root.right);
        res.push(root.val);
        dfs(root.left);
    }

    let res: Array<number> = [];
    dfs(root);

    return res[k - 1];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 二叉搜索树的第k大节点
  2. 2. 解题思路：dfs+逆中序
  3. 3. 复杂度：
  4. 4. 代码实现：