LeetCode 236. 二叉树的最近公共祖先 [Hot 100]

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

中等

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

百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

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

代码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件
        if (root == null) return null;
        if (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：只有左子树包含p或q
        if (left != null) {
            return left;
        }
        
        // 情况3：只有右子树包含p或q
        if (right != null) {
            return right;
        }
        
        // 情况4：左右子树都不包含p和q
        return null;
    }
}

递归法（后序遍历）

核心思想：

• 从底向上遍历（后序遍历）
• 如果当前节点是 p 或 q，则返回该节点
• 如果左右子树分别包含 p 和 q，则当前节点就是 LCA
• 如果只有一侧有非空结果，说明 LCA 在那一侧

递归函数定义：
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
返回：以 root 为根的子树中包含 p 或 q 的节点，如果都不包含则返回 null。

详细步骤

1. 递归终止条件：

   • 如果 root 为 null，返回 null
   • 如果 root 等于 p 或 q，返回 root（因为找到了目标节点）

2. 递归左右子树：

   • left = LCA(root.left, p, q)
   • right = LCA(root.right, p, q)

3. 判断情况：

   • 如果 left 和 right 都不为空 → root 是 LCA
   • 如果 left 不为空，right 为空 → 返回 left
   • 如果 right 不为空，left 为空 → 返回 right
   • 如果都为空 → 返回 null

示例推演

以二叉树 [3,5,1,6,2,0,8,null,null,7,4] 为例，找节点 5 和 1 的 LCA：

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

递归过程：

1. LCA(3,5,1)：

   • 左子树：LCA(5,5,1) → 找到5，返回5
   • 右子树：LCA(1,5,1) → 找到1，返回1
   • 左右都不为空 → 返回3（LCA）

找节点 5 和 4 的 LCA：

1. LCA(3,5,4)：

   • 左子树：LCA(5,5,4)：

     • 左子树：LCA(6,5,4) → 不包含，返回null

     • 右子树：LCA(2,5,4)：

       • 左子树：LCA(7,5,4) → null
       • 右子树：LCA(4,5,4) → 找到4，返回4
       • 左右：null和4 → 返回4
     • 当前节点5等于p → 返回5
     • 左右：null和4 → 但当前节点是5，所以返回5
   • 右子树：LCA(1,5,4) → 不包含，返回null
   • 左右：5和null → 返回5（LCA）