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

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

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

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

本站部分内容来源互联网,如果有图片或者内容侵犯您的权益请联系我们删除!

相关文档推荐

Update another component when Formik form changes(当Formik表单更改时更新另一个组件)
Formik validation isSubmitting / isValidating not getting set to true(Formik验证正在提交/isValiating未设置为True)
React Validation Max Range Using Formik(使用Formik的Reaction验证最大范围)
Validation using Yup to check string or number length(使用YUP检查字符串或数字长度的验证)
Updating initialValues prop on Formik Form does not update input value(更新Formik表单上的初始值属性不会更新输入值)
password validation with yup and formik(使用YUP和Formick进行密码验证)