在JavaScript中寻找BST中最接近的值

Question

试着跟这一起写在在二进制搜索树中找到最接近的值上。然而，我得到的是未定义的返回，而不是13。下面是包含树数据的代码。编写有另一种更优化的解决方案，但我只是尝试首先了解优化程度较低的版本。我错过了一步，但找不到。我错过了什么。谢谢。

[

​

const treeData = {
  "target": 12,
  "tree": {
      "nodes": [
        {"id": "10", "left": "5", "right": "15", "value": 10},
        {"id": "15", "left": "13", "right": "22", "value": 15},
        {"id": "22", "left": null, "right": null, "value": 22},
        {"id": "13", "left": null, "right": "14", "value": 13},
        {"id": "14", "left": null, "right": null, "value": 14},
        {"id": "5", "left": "2", "right": "5-2", "value": 5},
        {"id": "5-2", "left": null, "right": null, "value": 5},
        {"id": "2", "left": "1", "right": null, "value": 2},
        {"id": "1", "left": null, "right": null, "value": 1}
      ],
      "root": "10"
    }
};
  
class BST {
    constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
};


const findClosestValueInBst = (tree, target) => {
  
  // define current node as input tree
    let currentNode = tree;
  //console.log(tree);
  // create array to store BST values
  const values = [];

  // traverse the tree and place all values in the above array
    const traverse = node => {
    if (node) {
        traverse(node.left);
      values.push(node.value);
      traverse(node.right);
    }
  }
  
  traverse(tree);
  
  // create closestProximity variable
  let closestProximity = Number.POSITIVE_INFINITY;
  //console.log(closestProximity);
  // create undefined closestValue variable
  let closestValue;
  
  // iterate over the values array, checking each value's proximity to the target value
  for (let i = 0; i < values.length; i++) {
    let proximity = Math.abs(values[i] - target);
    // if closer in proximity than closestProximity, replace closestProximity
    if (proximity < closestProximity) {
        // update closestValue
      closestValue = values[i];
    }
    
  }

 
  return closestValue;
};

const result = findClosestValueInBst(treeData.tree, treeData.target);
console.log(result);

​

]2

Answer 1

在对你的问题作了更正之后，仍然存在以下问题：

• 代码从不更新closestProximity，因此该变量上的if条件将始终为真。
• 主调用将treeData.tree传递给函数，但该函数将该引用视为节点对象，从不查看nodes属性。
• 输入数据不会转换为BST实例，这意味着您无法有效地在树中导航。即使您有一个node对象，node.left也只是一个字符串，而不是一个对象，您必须扫描tree.nodes数组才能找到相应的对象。
• 首先通过traverse将节点收集到数组中，就会失去二进制搜索树的任何好处。此数据结构的目的是避免访问所有值。

下面是针对这些问题的代码更正：

​

class BST {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function loadTree(tree) {
    const nodeMap = new Map(tree.nodes.map(node => [node.id, new BST(node.value)]));
    for (const node of tree.nodes) {
        nodeMap.get(node.id).left = nodeMap.get(node.left) ?? null;
        nodeMap.get(node.id).right = nodeMap.get(node.right) ?? null;
    }
    return nodeMap.get(tree.root);
}

function findClosestValueInBst(root, target) {
    let currentNode = root;
    let high = Infinity;
    let low = -Infinity;
    while (currentNode) {
        if (target < currentNode.value) {
            high = currentNode.value;
            currentNode = currentNode.left;
        } else {
            low = currentNode.value;
            currentNode = currentNode.right;
        }
    }
    return high - target < target - low ? high : low;
}

const treeData = {"target": 12,"tree": {"nodes": [{"id": "10", "left": "5", "right": "15", "value": 10},{"id": "15", "left": "13", "right": "22", "value": 15},{"id": "22", "left": null, "right": null, "value": 22},{"id": "13", "left": null, "right": "14", "value": 13},{"id": "14", "left": null, "right": null, "value": 14},{"id": "5", "left": "2", "right": "5-2", "value": 5},{"id": "5-2", "left": null, "right": null, "value": 5},{"id": "2", "left": "1", "right": null, "value": 2},{"id": "1", "left": null, "right": null, "value": 1}],"root": "10"}}; 
const result = findClosestValueInBst(loadTree(treeData.tree), treeData.target);
console.log(result);

​