二叉树的最近公共祖先

给定一棵普通二叉树和树中的两个节点 p、q，返回它们的最近公共祖先。

最近公共祖先同时是 p、q 的祖先，并且深度尽可能大。题目定义允许节点是自己的祖先，所以答案可能等于 p 或 q。

• • 这是一棵普通二叉树，不保证左小右大。
• • p、q 不同且都存在于树中。
• • 答案是节点引用，不只是一个布尔值或节点值。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
边界示例：p = 5, q = 4 时输出 5。

把函数理解成对子树的询问：“你这里有没有 p、q，或者是否已经找出了 LCA？”子树只需要返回一个 TreeNode 指针。

返回 nil 表示没有目标；返回 p 或 q 表示找到一个目标；返回其他节点则表示这棵子树内部已经合并出了最终 LCA。

路径法对 p、q 各做一次 DFS，保存从根到目标的节点数组，再线性比较公共前缀。时间仍是 O(n)，但需要 O(h) 路径并维护 push/pop。

更不合适的误区是根据 p.Val、q.Val 与 root.Val 选择方向。这只有 LC235 的 BST 才成立，普通二叉树的值与位置没有关系。

pathP = [3,5]
pathQ = [3,1]
最后一个相同节点 = 3

普通二叉树没有 BST 的值域路牌，因此根节点无法提前选择方向。解决办法是把问题改写成通信协议：每棵子树搜索完以后，向父节点返回一个节点信号。

递归先处理基础条件，再分别获得 left、right。两侧都返回非空信号时在当前节点合并；只有一侧非空时原样上传；两侧都空时自然返回 nil。

• • 向下阶段：把同一个问题交给左右子树。
• • 向上阶段：解释每个子树找到的有效信号。
• • 合并阶段：第一处左右都非空的位置就是答案。

`nil` 表示当前子树没有发现目标；返回 p 或 q 表示发现了其中一个目标；返回其他节点表示更深处已经形成 LCA，当前层只负责继续上报。

这个协议把“是否找到”和“找到的是谁”合在一个节点指针中。若只返回 bool，父节点无法区分找到 p、找到 q，还是已经找到最终答案。

left=nil, right=nil   → return nil
left=5, right=nil     → return 5
left=nil, right=1     → return 1
left=5, right=1       → return current root

基础条件先截住空节点和目标节点。只有普通节点才继续递归左右子树，因此决策发生在两个孩子都完成之后，这正是后序思路。

left 与 right 同时非空说明两条目标路径第一次在当前 root 汇合；只收到一条信号时，当前节点还不能证明自己是答案，只能把已有信号继续交给父节点。

• • 基础条件：`root == nil || root == p || root == q`。
• • 双非空：`return root`。
• • 单非空：返回非空一侧；双空也会返回 nil。

先处理 nil 与命中目标的基础情况；再递归计算 left 和 right；最后根据两个返回值做合并。

若 left、right 都非空返回 root，否则 left 非空就返回 left，剩下情况返回 right。right 也可能是 nil，正好覆盖双空。

left 非空说明左子树包含 p、q 中至少一个目标或已经形成的 LCA；right 非空同理。题目只有两个目标，因此两侧同时非空时，两个目标分别落在当前节点两侧。

当前 root 能同时覆盖左右两侧目标。任何比 root 更低的节点都只能属于左子树或右子树之一，不可能跨过 root 同时覆盖另一侧，所以 root 就是最低公共祖先。

若只有一侧非空，两个目标可能都在那一侧，也可能目前只找到一个；无论哪种情况，当前 root 都没有足够证据成为答案，原样上传是唯一安全动作。