树与图中等1 种解法

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

在普通二叉树中寻找两个给定节点的最近公共祖先。

#二叉树#深度优先搜索#后序遍历

解题主线

后序返回值表示当前子树是否找到了 p 或 q；左右均非空时当前根就是答案。

解法 1：后序递归汇总

分别向左右查找；两侧都有结果返回根，否则向上传递非空侧。

时间复杂度

O(n)

空间复杂度

O(h)

236. 二叉树的最近公共祖先 · 后序递归汇总

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

分别向左右查找；两侧都有结果返回根，否则向上传递非空侧。

边界与易错点

命中 p 或 q 时应立即返回当前节点，使祖先能够汇总两侧结果。
两个来源中的同质实现只保留一次。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q235_236_lowestCommonAncestor.javaleetcode/src/main/java/tree/Q236_lowestCommonAncestor.java