二叉搜索树(BST)查找最接近目标值代码错误调试

• 递归判断遍历方向时，错误使用根节点tree的value做比较，而非当前遍历节点inputTree的value。
  你代码中的分支判断逻辑if (target < tree.value)里的tree是函数入口传入的根节点，值不会随着递归遍历的节点变化，导致遍历方向完全错误。比如你测试用例的根节点如果是10，目标值12永远大于根节点值，所以每一层递归都会判定走右子树，到15节点时本应走左子树找13，却错误继续走右子树到22，最终得到错误结果。

只需要把分支判断的对比对象从tree改为当前遍历节点inputTree即可，修正后的完整代码如下：

function findClosestValueInBst(tree, target) {
    let closest = tree.value;
    const traverse = (inputTree) => {
        if (inputTree === null) return;
        // 更新最近值
        if (Math.abs(target - closest) > Math.abs(target - inputTree.value)) {
            closest = inputTree.value;
        }
        // 修正：和当前节点的值对比判断遍历方向
        if (target < inputTree.value) {
            traverse(inputTree.left);
        } else {
            traverse(inputTree.right);
        }
    }
    traverse(tree);
    return closest;
}

// This is the class of the input tree. Do not edit.
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

• 可以去掉递归改用迭代实现，避免递归深度过大时出现栈溢出问题，空间复杂度从平均O(logn)、最坏O(n)降到O(1)
• 当遇到和目标值完全相等的节点时可以提前终止遍历，减少不必要的计算

内容的提问来源于stack exchange，提问作者Sebastian Carazo