面试题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}
 */
const kthLargest = function (root, k) {
  const 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}
 */
const 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
}

题链