二叉搜索树遍历-查找最接近的值 [英] Binary Search Tree traversal - Find Closest Value

问题描述

我正在做一个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。

推荐答案

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

在这种情况下，最好对参数进行更明确的命名，这样就不会出现念力。

这篇关于二叉搜索树遍历-查找最接近的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！