二叉搜索树遍历 - 找到最接近的值

Question

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

这是提示

Write a function that takes in a Binary Search Tree (BST) and a target integer value and returns the closest value to that target value contained in the BST. Each BST node has an integer value, a left child node, and a right child node. Its children's are valid BST nodes themselves or None / Null

目标：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，所以它 returns 10 作为可能的关闭值而不是 13，它具有绝对值比 10 更接近 12。

Answer 1

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;
}

在这种情况下，将参数命名得更清楚会有所帮助，这样就不会出现混淆。

Answer 2

也许这行得通。

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

然后它查找是否找到了目标并且 returns 目标。

否则检查目标是否在里面

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

使用 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}

closer 助手简单地选择两个数字中哪个更接近目标，如果它们同样接近，则任意选择第二个。

如果提供的树是 null，主函数简单地以无限值转义，然后根据我们的 target 是否等于、小于或大于当前节点的值进行分支.如果 equal，我们就完成了并且 return 节点的值。如果less than，我们在左分支上循环，然后选择该结果和节点值中更接近的那个，同样，如果greater than，我们对右分支做同样的事情。

请注意，我的答案可能与 Nina 的不同，因为我们会做出不同的任意选择，比如 11 或 13 更接近 12。

二叉搜索树遍历 - 找到最接近的值

Binary Search Tree traversal - Find Closest Value

javascript

algorithm

recursion

binary-search-tree