二叉树的最近公共祖先
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先（LCA）。
最近公共祖先的定义为：「对于有根树 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
模拟答题者思考
1. LCA 的本质：从下往上找「第一个同时拥有 p 和 q 的节点」。
2. 后序遍历：先拿到左右子树的结果，再决定当前节点是不是答案。
3. 三种情况：(a) L 和 R 都非空 → root 就是 LCA；(b) 只有一个非空 → 把非空的传上去；(c) 都空 → 返回 null。
4. 特殊：当前节点 == p 或 q 时直接返回自己（不必再看子树）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
L | TreeNode* | 定义：左子树的递归返回值 维护：若左子树包含 p 或 q 则返回该节点，否则返回 null 更新：L = dfs(root.left, p, q) |
R | TreeNode* | 定义：右子树的递归返回值 维护：若右子树包含 p 或 q 则返回该节点，否则返回 null 更新：R = dfs(root.right, p, q) |
落码步骤
1. 若 root == null or root == p or root == q，返回 root
2. L = dfs(root.left)，R = dfs(root.right)
3. 若 L != null and R != null，返回 root（此时 root 就是 LCA）
4. 否则返回 L or R（把找到的 p/q 向上传）
代码实现
class Solution:
def lowestCommonAncestor(
self, root: TreeNode, p: TreeNode, q: TreeNode
) -> TreeNode:
if not root or root == p or root == q:
return root
L = self.lowestCommonAncestor(root.left, p, q)
R = self.lowestCommonAncestor(root.right, p, q)
if L and R:
return root # p 和 q 分别在左右子树中
return L or R # p 和 q 在同一个子树中，或都未找到class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q)
return root;
TreeNode* L = lowestCommonAncestor(root->left, p, q);
TreeNode* R = lowestCommonAncestor(root->right, p, q);
if (L && R) return root; // p 和 q 分别在左右子树
return L ? L : R; // p 和 q 在同一子树，或都未找到
}
};
// 时间 O(n)，空间 O(n)（递归栈）复杂度分析
时间复杂度
O(n)
空间复杂度
O(n)
常见坑
判断 L 和 R 都非空才返回 root——这是 LCA 的唯一判定条件，不要过早返回。
当前节点等于 p 或 q 时直接返回当前节点：因为一个节点可以是自己的祖先。
BST 版本（LC235）可以用值比较剪枝，普通二叉树必须遍历整棵树。
必测边界 Case
Case 1：p 是 q 的祖先
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 → 输出 5
Case 2：p 和 q 相同
p == q → 输出 p