二叉树的最近公共祖先——后序遍历的状态返回技巧

老张2026/4/30大约 8 分钟

二叉树的最近公共祖先——后序遍历的状态返回技巧

适读人群：Java 后端工程师、准备面试的同学 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

236 题是我面试阶段碰到频率最高的树的题目之一，没有之一。但这道题有意思的地方不在于"会不会做"，而在于"能不能说清楚为什么这样做"。

很多人能写出答案，但如果面试官追问"你的递归返回值是什么含义？你怎么知道什么时候要返回 p 或 q 本身？"就说不清楚了。

我第一次研究这道题的时候，花了很长时间才想清楚：这道题的精髓在于"后序遍历的状态返回"——递归函数的返回值不只是一个答案，它携带了子树里关于 p 和 q 的信息，帮助父节点做出判断。

理解了这一点，这道题的代码就显得非常自然，而不是"背答案"。

一、题目解析

题目：LeetCode 236. 二叉树的最近公共祖先

给定一个二叉树，找到该树中两个指定节点的最近公共祖先（LCA）。

最近公共祖先的定义：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

示例：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3（节点5和节点1的最近公共祖先是节点3）

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5（节点5是节点4的祖先，也是其自身的祖先，所以LCA是5）

输入：root = [1,2], p = 1, q = 2
输出：1

约束：树中节点数目在 [2, 10^5] 范围内，p != q，p 和 q 都存在于树中。

考点梳理：

LCA 的两种情况：p 和 q 在同一子树 vs 分别在左右子树
后序遍历返回状态的含义和设计
路径记录法（暴力）
迭代版本的实现

二、解法一：暴力解法——路径记录法

思路

分别从根节点到 p 和 q 记录路径，然后找两条路径的最后一个公共节点。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        
        // 找最后一个公共节点
        TreeNode lca = null;
        int i = 0, j = 0;
        while (i < pathP.size() && j < pathQ.size()) {
            if (pathP.get(i) == pathQ.get(j)) {
                lca = pathP.get(i);
                i++;
                j++;
            } else {
                break;
            }
        }
        
        return lca;
    }
    
    private boolean findPath(TreeNode node, TreeNode target, List<TreeNode> path) {
        if (node == null) return false;
        path.add(node);
        if (node == target) return true;
        if (findPath(node.left, target, path) || findPath(node.right, target, path)) return true;
        path.remove(path.size() - 1);  // 回溯
        return false;
    }
}

复杂度分析

时间复杂度：O(n)。两次 DFS 各 O(n)。
空间复杂度：O(n)。路径长度最大 n，递归栈 O(n)。

三、解法二：父节点哈希表

思路

用 BFS 或 DFS 记录每个节点的父节点。找到 p 和 q 之后，用 HashSet 记录 p 的所有祖先，然后从 q 开始向上找，第一个在 HashSet 里的节点就是 LCA。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        parentMap.put(root, null);
        
        // BFS 记录所有节点的父节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        // 直到 p 和 q 都在 parentMap 里，才可以停止
        while (!parentMap.containsKey(p) || !parentMap.containsKey(q)) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parentMap.put(node.left, node);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parentMap.put(node.right, node);
                queue.offer(node.right);
            }
        }
        
        // p 的所有祖先放入 Set
        Set<TreeNode> ancestors = new HashSet<>();
        TreeNode cur = p;
        while (cur != null) {
            ancestors.add(cur);
            cur = parentMap.get(cur);
        }
        
        // 从 q 向上找，第一个在 ancestors 中的节点就是 LCA
        cur = q;
        while (!ancestors.contains(cur)) {
            cur = parentMap.get(cur);
        }
        
        return cur;
    }
}

复杂度分析

时间复杂度：O(n)。BFS O(n)，向上找祖先 O(h)。
空间复杂度：O(n)。parentMap 存储所有节点。

四、解法三：最优解法——后序遍历状态返回

核心思想

定义递归函数的语义：

lowestCommonAncestor(node, p, q) 返回：

如果 node 子树内含有 p 或 q（或两者都有），返回它们中最靠上的那个（即 LCA 或 p 或 q 本身）
如果 node 子树内既没有 p 也没有 q，返回 null

状态分析：

设 left = 对左子树递归的返回值，right = 对右子树递归的返回值。

left != null && right != null：左子树有 p 或 q 中的一个，右子树有另一个，当前节点就是 LCA，返回当前节点
node == p || node == q：当前节点就是 p 或 q，它是自身的祖先，返回当前节点
left != null（right == null）：p 和 q 都在左子树里，返回 left（已经是 LCA 或 p/q 本身）
right != null（left == null）：p 和 q 都在右子树里，返回 right

Mermaid 图——后序递归状态传播

完整代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止：空节点返回 null；找到 p 或 q 本身，返回它
        if (root == null || root == p || root == q) return root;
        
        // 后序遍历：先处理左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 左右子树都找到了（p 和 q 分别在左右子树）：当前节点是 LCA
        if (left != null && right != null) return root;
        
        // 只有一侧找到了：返回那一侧的结果（可能是 LCA，也可能是 p 或 q 本身）
        return left != null ? left : right;
    }
}

为什么 root == p 时直接返回 root？

这里有个非常关键的隐含逻辑：题目保证了 p 和 q 都在树中。当我们递归到 root == p 时，有两种情况：

情况1：q 在 p 的子树里 此时 p 是 q 的祖先，p 就是 LCA。我们返回 p，然后上层调用看到非 null 的 left（或 right），最终返回 p。这是正确的。

情况2：q 在 p 的子树外 此时 LCA 一定在 p 的上方。我们返回 p，通知上层"在这边找到了 p 或 q 的其中一个"，上层再判断另一边是否有 q，从而确定 LCA。

也就是说，返回 root（当 root == p 时）的语义是"在我这个子树里找到了 p 或 q"，不一定是"p 就是 LCA"。LCA 的判断在上层做。

复杂度分析

时间复杂度：O(n)。后序遍历，每个节点访问一次。
空间复杂度：O(h)。递归栈深度为树的高度。

提交结果：时间击败约 100% 用户，空间击败约 70% 用户。

五、举一反三

LCA 的通用思路

public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root;  // 找到目标
    
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    
    if (left != null && right != null) return root;  // 分在两侧
    return left != null ? left : right;  // 在同一侧
}

六、踩坑实录

坑一：以为找到 p 或 q 就立刻停止全部递归

有人以为返回 root 当 root == p 时，整个递归就终止了，不会再往下走。这是错误的——返回的是这个递归函数的当前调用，右子树的递归调用（lowestCommonAncestor(root.right, p, q)）仍然会执行（在另一个调用帧里）。

坑二：无法区分"只在左找到"和"在左找到了 LCA"

返回值的语义决定了代码的正确性。这个递归函数的返回值可能是：LCA 节点、p 节点（表示在这个子树里找到了 p）、q 节点、null（表示没找到）。上层通过 left 和 right 是否为 null 来判断下一步。

坑三：BFS 父节点法在找到 p 和 q 之后没有停止 BFS

题目说 p 和 q 都存在于树中，但 BFS 可以在找到两者后提前停止，不需要遍历整棵树。虽然不影响正确性，但影响性能。

坑四：把 q 在 p 的子树里的情况漏考虑了

当 q 是 p 的子孙节点时，LCA 应该是 p。但如果代码在找到 p 时就返回 p（不继续向下搜索 q），那么递归会返回 p，上层看到 left = p，right = null，最终返回 p，这是正确的。代码的逻辑是自洽的，但需要理解清楚为什么。

坑五：235 题（BST 版 LCA）误用 236 题的代码

BST 的 LCA 有更高效的解法（利用 BST 的有序性，O(h) 时间 O(1) 空间），别把 236 题的通用解法直接套用在 235 题上，虽然正确但没有充分利用 BST 的性质。

七、总结

236 题最重要的理解点是"递归函数返回值的语义设计"。这道题的返回值不是简单的"是否找到了目标"，而是携带了子树搜索结果的信息，供上层节点做决策。

这种"后序遍历的状态返回"模式在树的题目里非常常见：

返回子树的某种信息（是否有 p、是否有 q、路径长度、节点数等）
当前节点根据左右子树的返回值做决策
决策结果继续向上返回

掌握了这个模式，类似 543（二叉树直径）、124（最大路径和）这些题的递归写法也会顺手很多。