1. 题目描述

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

示例 1:

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

示例 2:

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

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

2. 解题思路

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

复杂度分析：

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

  • 空间复杂度 O(n)，最差的情况下，也就是当树退化为链表时（全部为右子节点），系统使用 O(n) 大小的栈空间。

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val) {
    4. *     this.val = val;
    5. *     this.left = this.right = null;
    6. * }
    7. */
    8. /**
    9. * @param {TreeNode} root
    10. * @param {number} k
    11. * @return {number}
    12. */
    13. var kthLargest = function(root, k) {
    14.   let res = []
    16.   const dfs = (root) => {
    17.       if(!root){
    18.           return 
    19.       }
    21.       dfs(root.right)
    22.       res.push(root.val)
    23.       dfs(root.left)
    24.   }
    25.   dfs(root)
    27.   return res[k - 1]
    28. };

    4. 提交结果

    image.png