You need to enable JavaScript to run this app. 二叉树最近公共祖先(LCA)实现:为何控制台输出正确但返回值始终为undefined
优惠活动
大模型
产品
解决方案
定价
更多

二叉树最近公共祖先(LCA)实现:为何控制台输出正确但返回值始终为undefined

根因分析

你碰到的“控制台打印了正确的匹配值,但函数始终返回undefined”的问题,是三个不严谨的实现细节叠加导致的:

1. Map对象的误用

你声明父节点映射时用了new Map(),但记录父节点关系时直接通过方括号赋值的方式写入值,比如hash[node.right.val] = node.val。这种写法本质是给Map实例动态挂了一个普通的对象属性,并没有写入Map的内部存储结构——虽然在非严格模式下能暂时读到这些自定义属性值,但这种写法完全不符合Map的使用规范,极易出现键值丢失、读取异常的问题。

2. 路径构建的边界漏洞

你初始化路径数组时直接默认hash[q.val]、hash[p.val]一定有值:let path1 = [q.val, hash[q.val]]、let path2 = [p.val, hash[p.val]]。这里漏掉了最核心的边界情况:

  • 当p或q本身就是根节点时,根节点没有父节点,对应哈希里根本没有这个键,读出来的值是undefined
  • 后续补全路径的循环会反复判断“路径最后一个元素是否等于根节点值”,碰到undefined会触发无限循环,不停往数组里pushundefined,最终因为栈溢出中断执行

3. 函数返回值的缺失

你的整个函数只有在for循环命中if判断的时候才会执行return,一旦因为前面的问题导致路径构建异常、匹配逻辑没走到if分支,代码会直接走完整个函数体,没有任何兜底返回值,默认就会返回undefined。你之前看到console.log打印出正确值,只是单次运行刚好命中了if分支,但由于实现本身不健壮,其他测试路径下会直接跳过return逻辑,最终返回undefined。

修复参考

你可以把实现调整成以下健壮版本:

var lowestCommonAncestor = function(root, p, q) {
    const stack = [root];
    // 直接用普通对象存父节点映射,避免Map的API误用问题
    const parentMap = {};
    // 显式给根节点记录父节点为null,补全边界
    parentMap[root.val] = null;

    // 遍历整棵树,记录每个非根节点的父节点
    while (stack.length) {
        const node = stack.pop();
        if (node.right) {
            parentMap[node.right.val] = node.val;
            stack.push(node.right);
        }
        if (node.left) {
            parentMap[node.left.val] = node.val;
            stack.push(node.left);
        }
    }

    // 构建p节点从自身到根节点的完整路径
    const pathP = [];
    let current = p.val;
    while (current !== null) {
        pathP.push(current);
        current = parentMap[current];
    }

    // 从q节点开始向上回溯,第一个出现在p路径中的节点就是最近公共祖先
    current = q.val;
    while (current !== null) {
        if (pathP.includes(current)) {
            return current;
        }
        current = parentMap[current];
    }
};

内容的提问来源于stack exchange,提问作者Daniel Lancaster

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.02 19:36:08