Meta 带parent指针的LCA：常数空间相遇

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 每节点parent指向唯一父，根parent=None，父链无环。两节点可以相同，也可能在不同树，后者返回None。
• 不按val判断相等，两个不同节点可以有相同值；原children指针不必遍历。

解题路线

1. 把两条节点到根再到None的链看作可能相交的链表。a到None后切换到second，b到None后切换到first，直到对象相同。
2. 两指针各走同样的两链总长度，长度差被换链消除；若共享祖先链，在第一个共享节点相遇；没有共享链则在None相遇。
3. 也可先计父链深度、对齐后一起上移，O(1)空间同样成立；示例换链法更短但必须明确None处理。

手动走一遍

根R有子A/B，A下有C。C与B最近公共祖先R；C与A得到A；C与C得到C。另一个独立根X与C结果None。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def lca_with_parent(first, second):
    """Proper acyclic parent chains. Distinct trees return None; compare identity."""
    a,b=first,second
    while a is not b:
        a=a.parent if a is not None else second
        b=b.parent if b is not None else first
    return a

复杂度

O(h_first+h_second)时间/O(1)辅助空间，退化深链线性；不依赖树平衡。

易错点与追问

容易失分的边界

• 比较node.val会把同值不同节点误当公共祖先。
• 父链有环时算法可能不结束；本题树前提不支持一般有向图。

继续深挖

• 要返回所有共同祖先则需要按相遇点继续沿parent枚举，输出O(h)。
• 频繁静态LCA查询可二进制提升预处理，但空间和更新维护合同不同。