JavaScript实现BST最近值查找返回undefined问题求助

你的代码返回undefined的核心原因是：传入的treeData.tree不是BST类的实例结构，而是包含节点数组和root ID的原始数据集。你的traverse函数期望遍历的是带有left/right属性指向子BST节点的实例，但实际传入的tree里的节点left/right是字符串ID（比如"5"、"15"），不是BST对象，导致traverse函数无法正确遍历节点，最终values数组为空，closestValue始终是初始的undefined。

修复步骤 #

1. 先将原始节点数据转换为BST实例树 #

需要先把treeData里的节点数组转换成BST实例，并建立正确的父子节点引用：

// 辅助函数：将原始节点数据转换为BST树
function buildBST(treeData) {
  // 先把所有节点转成BST实例，用Map存储
  const nodeMap = new Map();
  treeData.nodes.forEach(node => {
    nodeMap.set(node.id, new BST(node.value));
  });
  // 为每个节点设置left和right引用
  treeData.nodes.forEach(node => {
    const bstNode = nodeMap.get(node.id);
    if (node.left) bstNode.left = nodeMap.get(node.left);
    if (node.right) bstNode.right = nodeMap.get(node.right);
  });
  // 返回根节点
  return nodeMap.get(treeData.root);
}

2. 修复遍历逻辑的严谨性 #

你的遍历逻辑本身没问题，但closestProximity没有在更新closestValue时同步更新，补充后逻辑更严谨：

const findClosestValueInBst = (tree, target) => {
  const values = [];

  const traverse = node => {
    if (node) {
      traverse(node.left);
      values.push(node.value);
      traverse(node.right);
    }
  }
  
  traverse(tree);
  
  let closestProximity = Number.POSITIVE_INFINITY;
  let closestValue;
  
  for (let i = 0; i < values.length; i++) {
    const proximity = Math.abs(values[i] - target);
    if (proximity < closestProximity) {
      closestProximity = proximity; // 同步更新最近距离
      closestValue = values[i];
    }
  }

  return closestValue;
};

3. 调用时传入转换后的BST根节点 #

// 先构建BST树
const bstRoot = buildBST(treeData.tree);
// 调用函数
const result = findClosestValueInBst(bstRoot, treeData.target);
console.log(result); // 输出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;
  }
};

// 辅助函数：构建BST树
function buildBST(treeData) {
  const nodeMap = new Map();
  treeData.nodes.forEach(node => {
    nodeMap.set(node.id, new BST(node.value));
  });
  treeData.nodes.forEach(node => {
    const bstNode = nodeMap.get(node.id);
    if (node.left) bstNode.left = nodeMap.get(node.left);
    if (node.right) bstNode.right = nodeMap.get(node.right);
  });
  return nodeMap.get(treeData.root);
}

const findClosestValueInBst = (tree, target) => {
  const values = [];

  const traverse = node => {
    if (node) {
      traverse(node.left);
      values.push(node.value);
      traverse(node.right);
    }
  }
  
  traverse(tree);
  
  let closestProximity = Number.POSITIVE_INFINITY;
  let closestValue;
  
  for (let i = 0; i < values.length; i++) {
    const proximity = Math.abs(values[i] - target);
    if (proximity < closestProximity) {
      closestProximity = proximity;
      closestValue = values[i];
    }
  }

  return closestValue;
};

const bstRoot = buildBST(treeData.tree);
const result = findClosestValueInBst(bstRoot, treeData.target);
console.log(result); // 13

内容的提问来源于stack exchange，提问作者larry8989