二叉树的最近公共祖先
🧠 问题描述：
给定一棵二叉树的根节点 root 和两个节点 p 和 q，请找出它们的 最近公共祖先节点。
公共祖先定义为：在树中，某个节点是 p 和 q 的祖先（包括自己），并且离它们尽可能近。
✅ 示例代码 + 中文注释
1class Solution {
2 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
3 // 递归终止条件：
4 // 如果当前节点为空，或者等于 p 或 q，则直接返回该节点
5 if (root == null || root == p || root == q) {
6 return root;
7 }
8
9 // 后序遍历：先递归查找左子树和右子树中是否包含 p 或 q
10 TreeNode left = lowestCommonAncestor(root.left, p, q);
11 TreeNode right = lowestCommonAncestor(root.right, p, q);
12
13 // 分析左右子树的查找结果
14 if (left == null && right == null) {
15 // 左右子树都没有找到 p 或 q，说明当前子树中不包含目标节点
16 return null;
17 } else if (left == null) {
18 // 左子树没找到，右子树找到了，说明 p 和 q 都在右子树中
19 return right;
20 } else if (right == null) {
21 // 右子树没找到，左子树找到了，说明 p 和 q 都在左子树中
22 return left;
23 } else {
24 // 左右子树各找到一个，说明当前节点就是它们的最近公共祖先
25 return root;
26 }
27 }
28}
📌 举个例子帮助理解：
假设有一棵树如下：
1 A
2 / \
3 B C
4 / \
5 D E
- 如果 p = D，q = E → 最近公共祖先是 B。
- 如果 p = D，q = C → 最近公共祖先是 A。
- 如果 p = B，q = A → 最近公共祖先是 A。
🧮 算法分析
- 时间复杂度：
O(n)
每个节点最多访问一次，n 是节点总数。 - 空间复杂度：
O(h)
h 是树的高度，主要取决于递归栈深度。
💡 总结递归逻辑：
| 情况 | 返回值 |
|---|---|
| 当前节点是 null 或 p/q | 返回当前节点 |
| 左右都为空 | 当前节点不是祖先，返回 null |
| 左空右非空 | 返回右边的结果 |
| 右空左非空 | 返回左边的结果 |
| 左右都有值 | 当前节点就是 LCA |