为什么我的二叉树Lowest Common Ancestor（LCA）函数始终返回null？

问题分析 #

你的LCA函数始终返回null，大概率是以下两个核心原因：

• 节点的parent指针未正确初始化：构建二叉树时，没给每个节点设置正确的父节点引用，导致getPathToRoot无法向上遍历到根，两个路径没有共同节点（除非s和t是同一个节点）。
• ArrayStack的操作逻辑与预期不符：如果ArrayStack的add是往栈顶加元素（类似栈的push），那getPathToRoot生成的路径顺序是根→父→目标节点，而你原有的findIntersection是从栈尾（根）开始比较，一旦两个节点不在同一分支，会直接匹配到根，但如果parent指针有问题，还是会返回null；如果栈顶是目标节点，原逻辑会直接比较两个目标节点，不相等就break，直接返回null。

修复步骤 #

1. 先检查并修复parent指针

这是最常见的问题，确保构建二叉树时，每个子节点的parent属性都指向父节点。例如添加子节点的代码：

// 示例：添加左子节点时必须设置parent
public void addLeftChild(Node parent, Node child) {
    parent.left = child;
    child.parent = parent; // 关键：给子节点绑定父引用
    stringsToNodes.put(child.s, child);
}

2. 修正路径与交集查找逻辑

如果ArrayStack是标准栈结构（push入栈顶、pop出栈顶），修改两个私有方法如下：

// 获取节点到根的路径（栈顶是目标节点，栈底是根）
private ArrayStack<Node> getPathToRoot(Node node) {
    ArrayStack<Node> path = new ArrayStack<>();
    while (node != null) {
        path.push(node); // 用push确保元素入栈顶
        node = node.parent;
    }
    return path;
}

// 查找两个路径的LCA节点
private Node findIntersection(ArrayStack<Node> pathS, ArrayStack<Node> pathT) {
    // 先把两个栈调整为相同长度
    while (pathS.size() > pathT.size()) {
        pathS.pop();
    }
    while (pathT.size() > pathS.size()) {
        pathT.pop();
    }

    // 同步弹出元素，找到第一个共同节点（也就是最深的共同祖先）
    while (!pathS.isEmpty()) {
        Node nodeS = pathS.pop();
        Node nodeT = pathT.pop();
        if (nodeS == nodeT) {
            return nodeS;
        }
    }
    return null; // 理论上不会走到这，因为根节点必然是所有节点的共同祖先
}

如果ArrayStack是类似List的结构（add往末尾加元素），可以保留原getPathToRoot，但必须确保parent指针正确，同时可以在getPathToRoot里加打印语句验证路径：

private ArrayStack<Node> getPathToRoot(Node node) {
    ArrayStack<Node> path = new ArrayStack<>();
    while (node != null) {
        path.add(node);
        System.out.println("路径节点：" + node.s); // 打印路径，确认是否能走到根
        node = node.parent;
    }
    return path;
}

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