题目重点：BST 用值域寻找两目标分叉处；推广到普通树时改为后序汇总目标出现数，并验证节点确实存在。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- BST 训练版值互异且两个目标值都存在；普通二叉树版接收两个 Node 对象，按身份而非数值判断，可处理值重复。
- 若普通树中任一目标缺失，返回 None；a 和 b 同一个对象且存在时返回该对象。
- 树无共享子节点/环；代码递归版对极深树可改显式后序栈。
解题路线
- BST：令 low=min(a,b)、high=max(a,b)。当前节点值若比 low 小，两目标都在右；若比 high 大，都在左；否则两目标分居或某一目标就是当前节点，它是 LCA。
- 普通树不能依靠数值大小。后序访问左右子树，返回候选节点及找到的目标数；两个目标在两侧或当前节点就是其中一个时，当前节点成为 LCA。
- 继续确保 found=2 才返回候选，可防一个目标缺失时误把唯一找到的节点当 LCA。若左右子树已找到完整答案可提前返回。
- 正确性来自普通树 LCA 是最深且包含两个目标的子树根；BST 分叉点则是首个把两个目标同时留在当前子树、却不能都下沉到同一儿子的节点。
手动走一遍
BST 根 6，目标 2 和 8 在根两边，LCA=6；目标 2 与其子孙 4，沿左路到 2 就停止，LCA=2。普通树若目标值都等于 5，也不能用值比较辨别，必须用两个具体 Node 身份。
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
复杂度
BST 时间 O(h)、迭代额外空间 O(1)，h 为树高；一般树必须最坏访问 O(n) 节点，递归栈 O(h)。缺失目标检查已包含一般树遍历。
易错点与追问
容易失分的边界
- 把 BST 的数值分叉规则直接用于普通二叉树。
- 一般树只找到一个目标时也返回该节点。
- 重复值树里只按 value 判断目标，识别错节点。
- 默认 BST 平衡而把最坏复杂度写成 O(log n)。
继续深挖
- 普通树有 parent 指针时怎样通过祖先集合求 LCA？
- 同一棵树大量 LCA 查询如何预处理？
- 树极深使递归栈溢出时怎样改写？
