好的，我们这次来详细讲解 LeetCode 第 236 题「二叉树的最近公共祖先」。
这是一道非常经典且高频的二叉树题目，我会从问题描述开始，一步步带你分析思路，并给出清晰的解法。

1. 题目描述

题目链接：LeetCode 236. Lowest Common Ancestor of a Binary Tree
难度：中等

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先（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
解释：节点 5 和节点 1 的最近公共祖先是 3。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是 5，因为根据定义，一个节点可以是自身的祖先。

注意：

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

2. 题意理解与关键点

公共祖先：节点 x 是 p 和 q 的公共祖先，意味着从根到 p 的路径和根到 q 的路径都会经过 x。
最近：在公共祖先中深度最大的那个。

关键点：

1. 如果 p 和 q 分别在某个节点 x 的左右子树中，那么 x 就是它们的最近公共祖先。
2. 如果 p 是 q 的祖先，那么 p 就是它们的最近公共祖先（反过来也一样）。
3. 题目保证 p 和 q 一定在树中，所以不需要考虑不存在的情况。

3. 思路分析

3.1 暴力思路（不推荐）

我们可以先分别记录从根到 p 和根到 q 的路径，然后找两条路径最后一个相同的节点。
这种方法需要存储路径，空间复杂度 O(h)，时间复杂度 O(n)，但实现略繁琐。

3.2 递归分治思路（最优）

我们可以用深度优先遍历（后序遍历）的思想：

递归定义：
函数 lowestCommonAncestor(root, p, q) 返回以 root 为根的树中 p 和 q 的最近公共祖先。

递归过程：

1. 如果 root 为空，返回 null。
2. 如果 root 等于 p 或 q，返回 root（因为 root 是 p 或 q 的祖先）。
3. 递归在左子树中找 p 和 q 的公共祖先，得到 left。
4. 递归在右子树中找 p 和 q 的公共祖先，得到 right。
5. 根据 left 和 right 的情况判断：
   • 如果 left 和 right 都不为空，说明 p 和 q 分别在 root 的左右子树中，那么 root 就是它们的最近公共祖先。
   • 如果 left 不为空，right 为空，说明 p 和 q 都在左子树，返回 left。
   • 如果 right 不为空，left 为空，说明 p 和 q 都在右子树，返回 right。
   • 如果都为空，返回 null。

4. 递归解法详细步骤

我们一步步模拟示例 2 来理解。

示例 2：
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

树结构：

        3
      /   \
     5     1
    / \   / \
   6   2 0   8
      / \
     7   4

p=5, q=4。

递归过程：

1. 从 root=3 开始：
   • 3 不是 p 或 q，递归左子树 root=5。
2. 在节点 5：
   • 5 就是 p，所以返回 5（表示在子树 5 中找到了 p 或 q）。
3. 回到节点 3 的左子树调用结束，得到 left=5。
4. 递归右子树 root=1：
   • 1 不是 p 或 q，递归左子树 root=0：
     • 0 不是 p 或 q，递归左子树 null → 返回 null，递归右子树 null → 返回 null，所以 0 返回 null。
   • 递归右子树 root=8：
     • 同理返回 null。
   • 所以 1 的左右都是 null，返回 null。
5. 回到节点 3：left=5, right=null，所以返回 left=5。

结果：5 是 p 和 q 的最近公共祖先。

5. 代码实现（Java）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果 root 为空，返回 null
        if (root == null) return null;
        
        // 如果 root 是 p 或 q，返回 root
        if (root == p || root == q) return root;
        
        // 递归在左子树和右子树中查找
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 如果左右都不为空，说明 p 和 q 在 root 的两侧，root 是 LCA
        if (left != null && right != null) return root;
        
        // 否则返回非空的那一边
        return left != null ? left : right;
    }
}

6. 复杂度分析

• 时间复杂度：O(n)，每个节点最多访问一次。
• 空间复杂度：O(h)，h 是树的高度，递归栈的深度。

7. 总结

这道题的核心是后序遍历和分治思想：

• 从底向上传递信息（是否找到 p 或 q）。
• 利用“最近”的特性，当 p 和 q 分布在某个节点的左右两侧时，该节点就是答案。
• 如果只在某一侧，则答案就在那一侧。

这个解法简洁高效，是二叉树 LCA 问题的标准解法。