二叉树最近公共祖先(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
相关产品推荐
相关产品推荐

