二叉树的最近公共祖先
Lowest Common Ancestor of a Binary Tree
在二叉树里找两个指定节点的最近公共祖先（一个节点也可以是自己的祖先）。
在力扣中练习题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点5和节点1的最近公共祖先是节点3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
解题思路
后序递归 · 自底向上汇报
每个节点只回答一件事：我这棵子树里有没有 p 或 q
从上往下搜索时，还不知道哪个节点会同时包含两个目标；后序递归可以让左右子树先汇报结果，再决定当前节点是否是答案。
自拟主例 root = [10,5,14,2,7,null,18,null,null,6,9]，p=6，q=9。答案是 7，既不是根，也不是某个目标自身。
命中目标 6，把该节点交回父调用。
子调用返回三类信息：空表示没找到；目标节点表示找到一个目标；其他非空节点表示子树内部已经找到了公共祖先。左右都非空时，当前节点就是两个目标首次汇合的位置。
7 找到答案以后，5 和 10 只原样向上传递节点 7，不能把更高的祖先覆盖成新答案。到空节点或目标自身就立即返回，这也覆盖了一个目标恰好是另一个祖先的情况。
易错点
- 把 root == p || root == q 放到递归后面判断：p 本身是 q 的祖先时，返回的会是 q 而不是 p。
- if (left && right) 写成 if (left || right)：只要求到一边就返回当前节点，答案会一路上浮到根。
- 最后写成 return root：把沿途所有祖先都当成了答案，只有一边有结果时必须返回那一边。
补出父指针 · 两条祖先链求交
记下每个节点的父亲，再从 p、q 分别往上走
正确的父指针映射做法，需要额外记录每个节点的父节点；用于对照向上查找与递归汇报。
既然缺的是父指针，那就先遍历一遍把父指针补出来：parent[child] = node。
然后这个问题就变成了「两条到根的路径，求第一个公共节点」：
- 从
p出发一路往上，把经过的节点（包括p自己）放进集合； - 从
q出发一路往上，第一个已经在集合里的节点就是答案。
为什么最近的？p 的祖先链是从 p 到根的一条路径。q 往上走时，越早遇到的节点离 q 越近，而第一个落在 p 祖先链上的节点，正是两条链第一次交汇的地方——再往上都是公共祖先，但都不如它近。
这个写法直白、不容易写错，代价是多花 O(n) 的哈希表存父指针。后序递归版不需要额外的表，只吃递归栈的空间，但要想清楚「每个节点该返回什么」。两者时间都是 O(n)。
- 1遍历整棵树，记录每个节点的父节点（根的父节点记为 nullptr）。
- 2从 p 往上一直走到根，把祖先链上的节点全部放进哈希集合。
- 3从 q 往上走，每走一步就查一次这个集合。
- 4遇到的第一个在集合里的节点就是最近公共祖先。
易错点
- 忘记把 p 自己放进集合：p 是 q 的祖先时会返回 p 的父节点。
- parent[root] 没有置空，往上走时读到野指针。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [10,5,14,2,7,null,18,null,null,6,9], p = 6, q = 9从根递归。子调用只返回空、某个目标，或已经找到的公共祖先。
查看 C++ 代码
延伸阅读
- 「先拿左右子树的结果，再决定自己返回什么」是树上的通用汇报模板：子树和、平衡性判断、树的直径都是这个形状。
- 如果树是二叉搜索树（235），可以直接用大小关系决定往哪边走，不需要后序遍历整棵树。
- 求两个节点的距离也能用它：dist = depth(p) + depth(q) - 2 × depth(lca)。