二叉树的最低公共祖先：有人知道为什么我的输出是未定义的吗？

Question

给定一棵二叉树，找到树中两个给定节点的最低公共祖先 (LCA)。

根据维基百科上LCA的定义：“最低共同祖先定义在两个节点p和q之间，作为T中同时具有p和q作为后代的最低节点（我们允许一个节点是一个自己的后代）。”

示例 1) 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和 1 的 LCA 为 3.

示例 2) 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和 4 的 LCA 为 5，因为根据 LCA 定义，节点可以是其自身的后代。

我的代码符合预期运行。当我遍历树时，我使用 hashMap 来跟踪 parent 个节点。然后在 while 循环中，我将我所采用的特定路径的 parent 节点推送到我的 p 和 q 输入节点。在我的 for 循环中，我遍历 parents 的路径并检查 parent 是否在第二条路径中。第一个 parent 匹配是 LCA。问题是我的输出总是未定义的。我在 for 循环中的 if 条件得到满足，我正在正确打印变量 num 。下一行是该数字的 return。但是我的输出仍然未定义。我可以 return 任何来自 True、“string”等的东西，而且我的输出不会从 undefined 改变。对此问题的任何见解表示赞赏。

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root] 
    let hash = new Map()
    
    while (stack.length) {
        let node = stack.pop() 
       
        
        if (node.right) {
            hash[node.right.val] = node.val
            stack.push(node.right)
        }
        
        if (node.left) {
            hash[node.left.val] = node.val
            stack.push(node.left)
        }
    }

    
    let path1 = [q.val, hash[q.val]]
    let path2 = [p.val, hash[p.val]]
   
    while (path1[path1.length - 1] !== root.val) { 
        path1.push(hash[path1[path1.length - 1]])
    }
    
     while (path2[path2.length - 1] !== root.val) {
        path2.push(hash[path2[path2.length - 1]])
    }
    
  
    for (let i = 0; i < path1.length; i ++) {
        let num = path1[i]
        if (path2.indexOf(num) !== -1) {
            console.log(num)
            return num
        }
        
    }
  
};

我的输入： [3,5,1,6,2,0,8,null,null,7,4], 7, 8

标准输出：3（正确）

输出：未定义

Answer 1

主要问题是你被要求return最低共同祖先：这不是一个值，而是一个节点。所以你不应该 return val 属性，而是属性.

的节点对象

这实际上意味着您应该从代码中删除对 val 属性的所有引用：它们是不相关的。

您的代码中还有两个问题：

一个 Map 对象有 set 和 get 方法。您而是在该对象上创建字符串属性。这是可行的，因为您通过 val 键入，但在上述观察之后，您将需要通过节点对象键入，因此您确实需要正确使用 Map.get 和 Map.set 方法。
您将 path1 和 path2 分别初始化为 2 个值。但是当 p 或 q 参数之一是根本身时，这会产生问题。您应该从 path1 和 path2 开始，每个元素只包含一个元素。循环将完成剩下的工作。

所以这里是你的代码更正：

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root];
    let hash = new Map();

    while (stack.length) {
        let node = stack.pop(); 

        if (node.right) {
            hash.set(node.right, node);
            stack.push(node.right);
        }

        if (node.left) {
            hash.set(node.left, node);
            stack.push(node.left);
        }
    }


    let path1 = [q];
    let path2 = [p];

    while (path1[path1.length - 1] !== root) { 
        path1.push(hash.get(path1[path1.length - 1]));
    }

    while (path2[path2.length - 1] !== root) {
        path2.push(hash.get(path2[path2.length - 1]));
    }

    for (let i = 0; i < path1.length; i ++) {
        let node = path1[i];
        if (path2.indexOf(node) !== -1) {
            return node;
        }
    }
}

注意：请养成以分号结束语句的习惯。确实没有充分的理由将其留给 automatic semicolon insertion 算法。你不会是第一个落入其中一个陷阱的人。

Answer 2

虽然这对您的回答没有帮助，但这是对问题的误读的有趣结果。我认为树只是由那些数组表示。这是可以做到的，我们当然可以在两种结构之间来回转换，用索引 n 处的节点的子节点是索引 2n + 1 和 2n + 2 处的节点，索引 n 处的节点的父节点（对于 n > 0）是 (n - 1) >> 1.

所以解决这个问题相当简单：

const paths = (n) => 
  [n, ...(n > 0 ? paths ((n - 1) >> 1) : [])]

const intersection = (xs, ys) => 
  xs .filter (x => ys .includes (x))

const lowestCommonAncestor = (xs, p, q) =>
  xs [Math .max (... intersection (paths (xs .indexOf(p)), paths(xs .indexOf (q))))]

console .log (
  lowestCommonAncestor ([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], 5, 4)
)
console .log (
  lowestCommonAncestor ([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], 5, 1)
)

但这与实际问题关系不大，因为在实际树中节点具有 val 以及可选的 left 和 right 属性。 Trincot很好的回答了原题

二叉树的最低公共祖先：有人知道为什么我的输出是未定义的吗？

Lowest Common Ancestor of a Binary Tree: Anyone know why my output is undefined?

javascript

algorithm

debugging

binary-tree