236. 二叉树的最近公共祖先

✅ 解题思路：递归（后序遍历）

我们采用 自底向上的递归策略（DFS 后序遍历）：

核心思想：

• 如果当前节点是 p 或 q，直接返回它（因为一个节点可以是自己的祖先）。
• 递归查找左子树和右子树：
  • 如果 左右子树都找到了目标节点（即 left != null && right != null），说明当前节点就是 LCA。
  • 如果只有一边找到，返回非空的那一边。
  • 如果都没找到，返回 null。

💡 关键理解：LCA 是第一个“同时包含 p 和 q”的节点。

🧠 递归终止条件

if (root == null || root == p || root == q) {
    return root;
}

• root == null：空节点，返回 null
• root == p || root == q：找到目标节点，返回自身

💡 Java 代码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 终止条件
        if (root == null || root == p || root == q) {
            return root;
        }

        // 递归左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 情况1：p 和 q 分别在左右子树 → root 是 LCA
        if (left != null && right != null) {
            return root;
        }

        // 情况2：只有一边有结果，返回非空的一边（可能为 LCA，也可能只是 p/q）
        return left != null ? left : right;
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n)
  最坏情况下需要遍历所有节点（n 为节点数）
• 空间复杂度：O(h)
  h 是树的高度，递归栈深度（最坏 O(n)，平衡树 O(log n)）

❗ 注意事项

• 题目保证 p 和 q 一定存在于树中，无需额外校验。
• 此解法适用于普通二叉树（不是 BST）。如果是 BST，可用更简单的值比较法（LeetCode 235）。

✅ 总结

这个递归解法是标准答案，务必掌握！