好的，我们这次来详细讲解 LeetCode 第 236 题「二叉树的最近公共祖先」。

1. 题目描述

题目链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

题目：
给定一个二叉树，以及该二叉树中的两个节点 p 和 q，要求找到它们的最近公共祖先（Lowest Common Ancestor, LCA）。

定义：
最近公共祖先是指同时为节点 p 和 q 的祖先，且在深度上尽可能深的节点（一个节点可以是自己的祖先）。

示例：

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

• 输入：p = 5, q = 1
  输出：节点 3
• 输入：p = 5, q = 4
  输出：节点 5（因为 5 是 5 和 4 的公共祖先，且深度最深）

注意：

• 所有节点值唯一。
• p 和 q 不同且均存在于二叉树中。

2. 思路分析

2.1 理解“最近公共祖先”

• 从根节点到 p 的路径，与根节点到 q 的路径，它们的最后一个公共节点就是 LCA。
• 如果 p 是 q 的祖先，那么 LCA 就是 p。
• 如果 q 是 p 的祖先，那么 LCA 就是 q。

2.2 初步思路

一个直观的想法是：

1. 分别记录从根到 p 和根到 q 的路径。
2. 比较两条路径，找到最后一个相同的节点。

但这样需要存储路径，空间复杂度 O(h)（h 为树高），而且需要两次遍历。

2.3 更优思路：一次后序遍历

我们可以在一次递归遍历中解决：

递归定义：
函数 lowestCommonAncestor(root, p, q) 返回：

• 如果当前子树包含 p 但不含 q，返回 p。
• 如果当前子树包含 q 但不含 p，返回 q。
• 如果当前子树同时包含 p 和 q，返回它们的最近公共祖先。
• 如果当前子树既不包含 p 也不含 q，返回 null。

关键推理：

• 从叶子往根方向进行后序遍历（左右根）。
• 如果当前节点是 p 或 q，则返回当前节点。
• 如果左子树返回非空，右子树返回非空，说明当前节点就是 LCA。
• 如果一边非空，一边为空，返回非空那边（表示这边有 p 或 q 或 LCA）。

3. 详细步骤推导

我们以示例树为例，p = 5, q = 4。

树结构：

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

递归过程（后序：左 → 右 → 根）：

1. 从根 3 开始，先递归左子树（以 5 为根的子树）：

   • 在 5 的左子树：节点 6 左右都空，返回 null。
   • 在 5 的右子树：节点 2 的左子树 7 返回 null，右子树 4 是 q，返回 4。
   • 节点 2 的左 null，右返回 4，所以 2 返回 4。
   • 回到 5：左 null，右返回 4，且 5 自身是 p，所以 5 返回 5（因为 p 和 q 在 5 的子树中，5 就是 LCA）。

2. 根 3 的右子树（以 1 为根）：

   • 遍历后，不包含 p 或 q，返回 null。

3. 根 3：左返回 5，右返回 null，所以返回 5。

最终 LCA 是 5。

4. 算法实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 递归终止条件
        if not root:
            return None
        if root == p or root == q:
            return root
        
        # 后序遍历：先左后右
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestAncestor(root.right, p, q)
        
        # 情况1：左右都不空，当前 root 是 LCA
        if left and right:
            return root
        
        # 情况2：一边不空，返回不空的那边（可能是 p、q 或 LCA）
        if left:
            return left
        if right:
            return right
        
        # 情况3：两边都空，返回 null
        return None

5. 复杂度分析

• 时间复杂度：O(N)，每个节点最多访问一次。
• 空间复杂度：O(H)，递归栈深度，最坏情况 O(N)（树退化为链表）。

6. 关键点总结

1. 后序遍历：从底向上查找，天然适合递归回溯。
2. 返回值含义：不是直接返回 LCA，而是返回“子树中是否包含 p 或 q 或 LCA”。
3. 四种情况：
   • 左右均非空 → 当前 root 是 LCA。
   • 左非空右空 → 返回左。
   • 左空右非空 → 返回右。
   • 左右均空 → 返回空。

7. 测试验证

用题目示例测试：

• p=5, q=1：在根 3 处，左返回 5，右返回 1，左右都不空 → 返回 3 ✅
• p=5, q=4：在 5 处，左 null，右返回 4，且自身是 5 → 返回 5 ✅

这样一步步推导，你应该能清晰理解这个题的解法了。需要我进一步解释某个细节吗？