81.二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 != q
- p 和 q 均存在于给定的二叉树中。
思路
把递归想成员工向上级汇报。
每个节点问自己的左、右两个下属同一个问题:
你那边的分支里，右没有找到p或q? 找到了就把结果报给我。
汇报上来只有三种情况:
- 左边报了，右边也报了
说明p和q分别在我的两侧，那我就是答案，再往上走公共祖先只会更远，再往下走就分开了。
- 左右一边报了
说明p和q都在那一边，我自己没什么好补充的，把那一边的结果原封不动往上传。
- 两边都没报
我这整块子树里啥都没有，向上报null
递归的终止条件:
- 走到null了，报null
- 当前节点就是p或q，直接报自己，不用再往下找了
/**
* 二叉树节点定义（LeetCode 已提供）
*/
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
class Solution {
/**
* 求二叉树中 p 和 q 的最近公共祖先
*
* 核心思想（"向上汇报"模型）：
* 每个节点问左右子树"你那边有没有 p 或 q"，然后根据两份汇报做判断：
* - 两边都有 → 我就是分叉点，我是答案
* - 只有一边 → 答案在那一边，原样往上传
* - 都没有 → 往上报 null
*
* 时间复杂度 O(n)：最坏情况每个节点访问一次
* 空间复杂度 O(n)：递归栈深度等于树高，链状树时退化为 n
*/
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
// ===== 终止条件 =====
// 1) 走到空节点：这条路上什么都没有
// 2) 当前节点正好是 p 或 q：直接返回自己，不再深入
// （即使另一个节点在我的子树里，答案也就是我，提前返回是安全的）
if (root == null || root == p || root == q) return root
// ===== 向下"派活"：分别问左右子树要汇报 =====
// 这是后序遍历——必须先拿到两边的结果，才能决定自己返回什么
val left = lowestCommonAncestor(root.left, p, q)
val right = lowestCommonAncestor(root.right, p, q)
// ===== 根据两份汇报做决策 =====
return when {
// 情况 1：p 和 q 分居两侧，当前节点就是最近公共祖先
left != null && right != null -> root
// 情况 2：只有左边有结果，把它原样上传
// （这个结果可能是 p/q 本身，也可能是深处已算出的 LCA）
left != null -> left
// 情况 3：右边有结果就传右边；两边都为 null 时 right 本身就是 null，
// 正好表示"我这块子树里啥也没有"，一举两得
else -> right
}
}
}
一定要注意这里是后序遍历，必须先递归左右子树拿到结果，再做判断。
如果你在if里先判断当前节点做别的事，逻辑就崩了。
这道题的本质是信息从下往上流。
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(n)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!