Meta 普通二叉树LCA：后序标记与缺失目标

题意与假设

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

• 有限无环二叉树、节点身份比较；允许两个目标相同。示例显式保证缺任一目标返回None，不将仅存在的另一个当LCA。
• 不依赖BST大小关系，目标值重复也合法。
• N叉变体用children列表替代left/right，仍按Node身份判定，缺任一目标返回None；first=second且存在返回该节点。

解题路线

1. 后序为每个节点汇总两目标是否出现的2位mask；本节点是first置位1，是second置位2，子树mask按位或。
2. 第一个后序达到mask3的节点就是最低覆盖两目标的节点，之后祖先仍mask3但不覆盖答案；若从未3则目标缺失。first==second时同一节点同时置两位，正确返回它。
3. 用显式(节点,done)栈避免深树递归限制，mask按id(node)索引，不要求Node类自带hash。此实现为成员校验保留O(n)mask，不能说O(h)空间。
4. N叉同一membership mask递推：当前目标位OR所有child mask。后序第一个mask=3的节点即最低共同祖先，无需把N叉硬转二叉；每child边只处理一次。代码额外提供lowest_common_ancestor_nary。

手动走一遍

root左右分别A/B，目标A/B得到root；目标A/外部同值节点A2得到None。常见递归“找到任一目标直接返回”若不另做成员校验，会错误把A当答案。 N叉根有三个child a/b/c，目标在a与c子树则根为LCA；两者在b同一支深处，后序先找到b子树内部答案并保留。

Python 参考实现

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

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

def lowest_common_ancestor(root, first, second):
    """Return None if either target is absent. Nodes are compared by identity."""
    if root is None or first is None or second is None:return None
    stack=[(root,False)];masks={};answer=None
    while stack:
        node,done=stack.pop()
        if not done:
            stack.append((node,True))
            if node.right is not None:stack.append((node.right,False))
            if node.left is not None:stack.append((node.left,False))
        else:
            mask=(1 if node is first else 0)|(2 if node is second else 0)
            mask |= masks.get(id(node.left),0)|masks.get(id(node.right),0)
            masks[id(node)]=mask
            if mask==3 and answer is None:answer=node
    return answer


def lowest_common_ancestor_nary(root,first,second):
    """Same membership contract, each node has a children list (no parents)."""
    if root is None or first is None or second is None:return None
    stack=[(root,False)];masks={};answer=None
    while stack:
        node,done=stack.pop()
        if not done:
            stack.append((node,True))
            for child in reversed(node.children):stack.append((child,False))
        else:
            mask=(1 if node is first else 0)|(2 if node is second else 0)
            for child in node.children:mask |= masks[id(child)]
            masks[id(node)]=mask
            if mask==3 and answer is None:answer=node
    return answer

复杂度

O(n)时间/O(n)辅助mask与栈。若保证两目标存在，可用递归返回候选、栈O(h)；成员计数可合并到递归返回tuple但仍受递归深度约束。

易错点与追问

容易失分的边界

• 用val匹配而非identity在重复值树中不可靠。
• 只找到一个节点的结果不能满足缺目标返回None的合同。

继续深挖

• 推广N叉树，汇总所有children mask；找到最低mask3节点的逻辑不变。
• 若目标集合有k个，位mask或计数汇总需避免目标重复；返回覆盖全部目标的最低节点。