我正在處理 AlgoExpert 挑戰，我已經花時間自己解決它，觀看了關于它的視頻講座，我覺得我有一個很好的理解，但是我現在在遞回和樹遍歷方面的技能非常低（這就是為什么我在做這個作業）。
這是提示
撰寫一個函式，該函式接受二叉搜索樹 (BST) 和目標整數值，并回傳與包含在 BST 中的目標值最接近的值。每個 BST 節點都有一個整數值、一個左子節點和一個右子節點。它的子節點是有效的 BST 節點本身或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;
}
}
The behavior so far is, traverse to Node 15, but then, instead of going to 13, it goes to 22 so it returns 10 as the closes possible value instead of 13 which has an absolute value closer to 12 than 10.
uj5u.com熱心網友回復：
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;
}
在這種情況下，將引數命名得更清楚是有幫助的，這樣就不會出現混淆。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359032.html
標籤：javascript algorithm recursion binary-search-tree
上一篇：檢查div的顯示CSS