二叉到N叉LCA：身份、缺失节点和子树标志

题意与假设

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

• 一般有根树children列表，按对象身份比较；重复value不等于同节点。
• p=q允许，若任一目标不在树里返回None；共享child或循环拒绝。

解题路线

1. 正向收集节点order并校验身份唯一，反序保证孩子先处理。每节点标志为本人命中位OR所有child位。
2. mask3表示同时含两目标，第一反序遇到的mask3节点即LCA，因为后续mask3只能在其祖先链上；保存最初答案。
3. 根mask不为3说明缺目标，返回None。这个缺失验证比简单“遇到p返回p”更完整；二叉树只是children数≤2特例。

手动走一遍

root左右子树分别含p/q，root是答案；同子树更深节点同时含两者，则取更深者。p=q在树中时节点自己的mask3，即自身；p存在、q缺失则None。

Python 参考实现

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

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

from dataclasses import dataclass,field


@dataclass(eq=False)
class Node:
    value:object
    children:list=field(default_factory=list)


def lca(root,p,q):
    if root is None:return None
    seen={id(root)};order=[root]
    for u in order:
        for v in u.children:
            if id(v) in seen:raise ValueError("not a tree")
            seen.add(id(v));order.append(v)
    flags={};answer=None
    for u in reversed(order):
        mask=(1 if u is p else 0)|(2 if u is q else 0)
        for v in u.children:mask|=flags[id(v)]
        flags[id(u)]=mask
        if mask==3 and answer is None:answer=u
    return answer if flags[id(root)]==3 else None

复杂度

O(n)时间/O(n)空间当前order/flags/seen；递归版O(h)栈但缺失检测仍要完整处理。静态多query可用Euler+RMQ或binary lifting。

易错点与追问

容易失分的边界

• 不能用value当身份导致相同键对象混淆。
• 目标缺失时把存在的一个节点当LCA，违背双目标合同。

继续深挖

• 父指针已提供时，集合/深度对齐算法如何省遍历？
• DAG有多父时为何LCA可能不唯一？