LeetCode 236. 二叉树的最近公共祖先（LCA）
📌 题目链接
- https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
💡 解题思路
本题要求在一棵 普通二叉树 中找到两个节点 p 和 q 的 最近公共祖先（LCA）。
最近公共祖先定义：
对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足：
- x 是 p 和 q 的祖先
- x 的深度尽可能大（离 p、q 最近）
🌳 核心思想：后序遍历（自底向上）
这是一道非常经典的 后序遍历（Left → Right → Root） 题目。由于是普通二叉树，无法利用大小关系剪枝，因此采用 后序遍历（左右根）。 只有当左右子树的递归结果都已知时，才能判断当前节点是否为最近公共祖先。
递归逻辑
对于当前节点 root：
递归终止条件
- 如果 root == null，返回 null
- 如果 root == p 或 root == q，直接返回 root（不再向下递归）
递归左右子树
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
根据左右返回值判断结果
- ✅ 左右都不为空 → root 就是 LCA
- ✅ 左不为空，右为空 → 返回左
- ✅ 右不为空，左为空 → 返回右
- ❌ 都为空 → 返回 null
🧠 为什么这样是对的？
情况一：p 和 q 分别在左右子树
root
/ \\
p q
- l != null, r != null
- 只有 root 能同时看到它们
- ✅ 返回 root
情况二：p 是 q 的祖先（或反过来）
p
\\
q
- 递归到 p 时直接返回
- 上层不会再找到第二个节点
- ✅ 返回 p
情况三：只在一个子树中
- 另一个子树返回 null
- 直接返回非空的那个结果
🧩 完整代码（Java）
/**
* Definition for a binary tree node.
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 1. 递归终止条件
if (root == null) return null;
if (root == p || root == q) return root;
// 2. 递归左右子树
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
// 3. 根据左右结果判断
if (l != null && r != null) return root; // p、q 分布在两侧
if (l == null && r != null) return r;
if (l != null && r == null) return l;
return null;
}
}
⏱ 复杂度分析
| 时间复杂度 | O(n) | 每个节点最多访问一次 |
| 空间复杂度 | O(h) | 递归栈深度，h 为树高 |
- 最坏情况（链状树）：O(n)
- 平衡二叉树：O(log n)
🔍 常见误区
| 必须先找 p 再找 q | ❌ 顺序无关 |
| 必须记录父节点 | ❌ 递归天然回溯 |
| 只适用于 BST | ❌ 本题是普通二叉树 |
| 返回第一个遇到的节点 | ❌ 要看左右子树结果 |
✅ 总结一句话
后序遍历 + 左右返回值判断，是二叉树 LCA 问题的通用解法。
