Amazon Coding：普通二叉树 LCA，目标缺失和同一节点怎么处理？

题意与假设

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

• 有限无环普通二叉树，目标是节点对象身份，不是value；两个目标可为同一个对象。
• 若任一目标不在树中返回None，这是比经典保证存在的版本更强的训练合同。源码同时含BST函数，BST函数仅在两个唯一值都存在时可用，并非普通树答案。

解题路线

1. 后序处理左右子树，每个结果包括candidate与found。found分别统计是否命中目标a和b；节点是a则加1、是b再加1，因此a=b时同一对象可同时满足两个目标。
2. 若某子树已找到2，返回它的candidate，它比当前节点更深；否则左右+本节点总命中2时当前就是最深汇合点。仅命中1时向上带候选，根处仍不足2则返回None。
3. 身份比较用is，重复值不会把不同节点错认成目标。若输入仅给value且存在重复，必须先确定目标唯一标识，而不是任意找到第一节点。
4. 树没有BST全局顺序，不能凭a/b值决定只搜左或右。若确为BST且目标保证存在，可用值区间找分叉，但这属于额外合同。
5. 深链会触发此递归实现的语言栈限制，可改显式后序栈存中间结果；单次查询O(n)，大量固定树查询才考虑Euler tour/RMQ或binary lifting预处理。

手动走一遍

根r的左右子树分别含a/b则LCA=r；a祖先于b则a；a=b返回a；相同value的外部新Node仍不在树中，应返回None。复用已验证实现：1,800随机普通树上36,000目标对与独立parent链交集对照，另1,800组缺失目标检查。

Python 参考实现

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

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

"""LCA by value in a BST and by identity in a general binary tree."""

from dataclasses import dataclass


@dataclass(eq=False)
class Node:
    value: int
    left: "Node | None" = None
    right: "Node | None" = None


def bst_lca(root: Node | None, a: int, b: int) -> Node | None:
    """Assumes both distinct values exist in the BST; duplicates are not supported."""
    low, high = min(a, b), max(a, b)
    current = root
    while current is not None:
        if high < current.value:
            current = current.left
        elif low > current.value:
            current = current.right
        else:
            return current
    return None


def binary_tree_lca(root: Node | None, a: Node, b: Node) -> Node | None:
    """Return None if either node is absent; compare node identity, not values."""
    def visit(node):
        if node is None:
            return None, 0
        left_node, left_found = visit(node.left)
        if left_found == 2:
            return left_node, 2
        right_node, right_found = visit(node.right)
        if right_found == 2:
            return right_node, 2
        own = int(node is a) + int(node is b)
        found = left_found + right_found + own
        if found >= 2:
            return node, 2
        return (left_node or right_node or (node if own else None)), found

    candidate, found = visit(root)
    return candidate if found == 2 else None

复杂度

普通树O(n)访问、O(h)递归栈，最坏h=n且可能超过Python递归限制。BST额外合同下O(h)时间/O(1)迭代空间；不能把这个复杂度套普通树。

易错点与追问

容易失分的边界

• 比较value而非节点身份。
• 有一个目标时直接返回它，却没核第二个存在。
• a=b只计一次导致错返回None。
• 普通树当BST只走一侧。

继续深挖

• 目标通过ID给定时怎样解析并验证？
• 百万节点深链怎样改迭代？
• 固定树千万次查询怎样预处理，更新树后如何处理失效？