2021-03-11 | 剑指 Offer 54. 二叉搜索树的第k大节点

淩亂°似流年 2022-11-12 01:49 89阅读 0赞

### 1. 题目描述 ###

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

**示例 1:**

输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 4

**示例 2:**

输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 4

**限制：** 1 ≤ k ≤ 二叉搜索树元素个数

### 2. 解题思路 ###

我们知道，二叉搜索树的中序遍历的结果是一个有大到小的数组，所以我们可以倒中序遍历，然后将第结果的第k大节点返回即可。

**复杂度分析：**

*  时间复杂度 O(n)，最差的情况下，也就是当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 n ，占用 O(n) 时间；
 *  空间复杂度 O(n)，最差的情况下，也就是当树退化为链表时（全部为右子节点），系统使用 O(n) 大小的栈空间。

### 3. 代码实现 ###

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @param {number} k * @return {number} */
    var kthLargest = function(root, k) { 
        let res = []
    
        const dfs = (root) => { 
            if(!root){ 
                return 
            }
    
            dfs(root.right)
            res.push(root.val)
            dfs(root.left)
        }
        dfs(root)
    
        return res[k - 1]
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210321225634449.png]

[20210321225634449.png]: /images/20221022/37c5ce3a6420472bb8e7163fc4b909c0.png?