二叉查找树遍历-查找最近值

Question

我正在做一个AlgoExpert挑战，我已经花时间自己解决它，看了关于它的视频讲座，我觉得我有一个很好的理解，但我在递归和树遍历方面的技能现在很低（这就是我工作的原因）。

这是提示

编写一个函数，该函数接受二进制搜索树（BST）和目标整数值，并返回与BST中包含的目标值最接近的值。每个BST节点都有一个整数值、一个左子节点和一个右子节点。其子节点本身是有效的BST节点或无/空

目标：12

这是我目前为止的解决方案:

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 < tree.value) {
            console.log('left')
            traverse(inputTree.left)
        } else {
            console.log('right')
            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;
  }
}

到目前为止的行为是，遍历到节点 15，但随后，它不是转到 13，而是转到 22，因此它返回 10 作为接近可能的值，而不是绝对值接近 12 而不是 10 的 13。

Answer 1

使用 Nina Scholz 的测试用例，但我认为这是一个更简单的递归，我们可以这样做：

const closer = (v) => (x, y) => 
  Math.abs (x - v) < Math .abs (y - v) ? x : y

const findClosestValueInBst = (node, target) =>
  node == null 
    ? Infinity
  : target == node .value 
    ? node .value
  : target < node .value
    ? closer (target) (findClosestValueInBst (node .left, target), node .value)
  : closer (target) (findClosestValueInBst (node .right, target), node .value)

const tree = { value: 10, left: { value: 7, left: { value: 5, left: null, right: null }, right: { value: 8, left: null, right: null } }, right: { value: 13, left: { value: 11, left: null, right: null }, right: { value: 15, left: null, right: null } } };

console .log (findClosestValueInBst (tree, 11))
console .log (findClosestValueInBst (tree, 12))
console .log (findClosestValueInBst (tree, 13))
console .log (findClosestValueInBst (tree, 14))
console .log (findClosestValueInBst (tree, 15))
console .log (findClosestValueInBst (tree, 16))

console .log (tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

Answer 2

也许这行得通。

它检查单个函数中的节点，并使用具有较大值的初始值的最后一个值。

然后它发现是否找到目标并返回目标。

否则，检查目标是否在内部

function findClosestValue(tree, target, last = tree.value) {
    if (tree === null) return last;
    
    if (tree.value === target) return target;
    
    if (
        last < target && target < tree.value ||
        tree.value < target && target < last    
    ) return Math.abs(target - this.value) < Math.abs(target - last)
        ? this.value
        : last;
    
    return target < tree.value
        ? findClosestValue(tree.left, target, tree.value)
        : findClosestValue(tree.right, target, tree.value);
}

const
    tree = { value: 10, left: { value: 7, left: { value: 5, left: null, right: null }, right: { value: 8, left: null, right: null } }, right: { value: 13, left: { value: 11, left: null, right: null }, right: { value: 15, left: null, right: null } } };

console.log(findClosestValue(tree, 11));
console.log(findClosestValue(tree, 12));
console.log(findClosestValue(tree, 13));
console.log(findClosestValue(tree, 14));
console.log(findClosestValue(tree, 15));
console.log(findClosestValue(tree, 16));
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

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;
        }
        // As you can see below this line you are checking target < tree.value
        // problem is that tree is the root that your surrounding function gets
        // not the argument that your recursive function gets.
        // both your condition and your parameter to traverse
        // need to be inputTree, not tree
        if (target < tree.value) {
            console.log('left')
            traverse(inputTree.left)
        } else {
            console.log('right')
            traverse(inputTree.right)
        }
        
    }
    traverse(tree)
    return closest;
}

现在看看下面的代码:

function findClosestValueInBst(root, target) {
    let closest = root.value;
  const traverse = (node) => {
        if (node === null) return;
        if (Math.abs(target - closest) > Math.abs(target - node.value)) {
            closest = node.value;
        }
        
        if (target < node.value) {
            console.log('left')
            traverse(node.left)
        } else {
            console.log('right')
            traverse(node.right)
        }
        
    }
    traverse(root)
    return closest;
}

在这种情况下，将参数命名得更清楚是有帮助的，这样就不会产生混淆。