Closest Binary Search Tree Value II

Description

null

Solution(javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
// /** 1: nlog(n) 或者 Heap klog(n)
//  * @param {TreeNode} root
//  * @param {number} target
//  * @param {number} k
//  * @return {number[]}
//  */
// const closestKValues = function (root, target, k) {
//   const aux = (node, list = []) => {
//     if (!node) {
//       return list
//     }
//     aux(node.left, list)
//     list.push(node.val)
//     aux(node.right, list)
//     return list
//   }
//   const list = aux(root)
//   return list
//     .sort((a, b) => Math.abs(a - target) - Math.abs(b - target))
//     .slice(0, k)
// }


/** 2: Two Stacks
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
const closestKValues = function (root, target, k) {
  const aux = (node, reverse, list = []) => {
    if (!node) {
      return list
    }
    aux(reverse ? node.right : node.left, reverse, list)
    if ((!reverse && node.val >= target) || (reverse && node.val < target)) {
      return list
    }
    list.push(node.val)
    aux(reverse ? node.left : node.right, reverse, list)
    return list
  }
  const predecessors = aux(root, false)
  const successors = aux(root, true)
  const result = []

  while (k > 0) {
    if (predecessors.length === 0) {
      result.push(successors.pop())
    } else if (successors.length === 0) {
      result.push(predecessors.pop())
    } else if (
      Math.abs(predecessors[predecessors.length - 1] - target) < Math.abs(successors[successors.length - 1] - target)
    ) {
      result.push(predecessors.pop())
    } else {
      result.push(successors.pop())
    }
    k--
  }
  return result
}