面试题54. 二叉搜索树的第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

JS

优化之前(O(n))

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function (root, k) {
    let res = []
    const middle = function (node) {
        if (node) {
            middle(node.left)
            res.unshift(node.val)
            middle(node.right)
        }
    }
    middle(root)
    return res[k - 1]
};

优化后

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function (root, k) {
    let res = 0
    const middle = function (node) {
        if (node) {
            middle(node.right)
            k--
            if (k===0) {
                res = node.val
                return
            }
            middle(node.left)
        }
    }
    middle(root)
    return res
};

题链