当前位置：首页 > news >正文

Hot 100 --- 二叉树的最近公共祖先

news 2026/7/21 0:43:38

本文概览：本文以LeetCode题目"二叉树的最近公共祖先"为例，讲解后序遍历+回溯汇总的思路，重点说明三种返回值情况的处理

一、题目

二、题目分析

题目要求：给定二叉树根节点root，以及两个节点p和q，找到它们的最近公共祖先

最近公共祖先的定义：设节点root为节点p、q的某公共祖先，若其左子节点root.left和右子节点root.right都不是p、q的公共祖先，则称root是"最近的公共祖先"

根据这个定义，判断一个节点是不是最近公共祖先，就要看它的左右子节点是不是公共祖先——如果左右子节点都不是公共祖先，那当前节点就是最近公共祖先。最典型的情况就是p和q分别位于当前节点的左右两侧

3 / \ 5 1 ← 3 是最近公共祖先（p=5 在左，q=1 在右） / \ \ 6 2 8

所以核心思路就是：后序遍历 + 回溯汇总。后序遍历先看左右子树，再把左右子树的结果汇总到当前节点做判断

思路概览

Java 实现代码如下

publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){returndfs(root,p,q);}privateTreeNodedfs(TreeNodenode,TreeNodep,TreeNodeq){// 如果当前节点为空，返回nullif(node==null){returnnull;}// 如果当前节点是p或q，返回当前节点if(node==p||node==q){returnnode;}// 递归搜索左子树TreeNodeleft=dfs(node.left,p,q);// 递归搜索右子树TreeNoderight=dfs(node.right,p,q);// 如果左子树和右子树都返回了非null值，说明当前节点是最近公共祖先if(left!=null&&right!=null){returnnode;}// 如果左子树或右子树返回了非null值，说明最近公共祖先在该子树中returnleft!=null?left:right;}

思路简要说明

整体是后序遍历 + 回溯汇总：

递归出口：当前节点为空返回 null；当前节点就是p或q，直接返回自身
后序遍历：先递归左子树、再递归右子树，拿到left和right两个返回值
三种情况汇总：
- left和right都不为 null →p、q分别在两侧，当前节点就是最近公共祖先
- left和right只有一个不为 null → 把这个非 null 的值往上返回，让上层节点继续判断
- left和right都为 null → 当前子树没找到，返回 null

核心就是每一步都把"子树里找到了什么"往上传，让上层节点做判断

三、思路详解

第一步：为什么是后序遍历？

要判断一个节点是不是最近公共祖先，必须先知道它的左子树和右子树里有没有p和q。也就是说先处理左右子树，再处理当前节点——这正是后序遍历（左→右→根）的顺序

3 / \ 5 1 后序遍历顺序：5 → 1 → 3 遍历到 3 时，已经知道左子树找到了 5，右子树找到了 1 → 3 就是最近公共祖先

如果是前序遍历（根→左→右），到了 3 还没遍历左右子树，根本不知道下面有没有p、q，没法判断

第二步：递归的两个出口

递归函数dfs(node, p, q)的作用是：在以node为根的子树中查找p和q，返回找到的节点（或最近公共祖先）

出口 1：node == null

遍历到空节点，说明走到底了没找到，返回 null

出口 2：node == p或node == q

当前节点本身就是p或q，直接返回自身。这里有一个关键点：一旦命中就直接返回，不再往下递归

为什么不往下递归？因为p（或q）已经找到了，它下面的子树再找也没意义。另一个节点只可能有两种位置：

在它的子树里：那p（或q）自己就是最近公共祖先（祖先可以包含自己）
不在它的子树里：那当前节点只是一个普通的目标节点，上层的其他分支会找到另一个，最后由上层汇总判断

不管哪种情况，当前节点只需要把自己返回给父节点就够了，不需要往下递归

第三步：左右子树返回值的三种情况

递归完左右子树后，拿到left和right两个返回值。这两个值有三种组合，每种对应一种情况：

情况 1：left != null && right != null（两边都不为空）

说明左子树找到了一个（p或q），右子树也找到了另一个。此时当前节点就是最近公共祖先——p和q分别在它的左右两侧

3 / \ 5 1 ← left=5, right=1，3 是最近公共祖先 / \ \ 6 2 8

返回当前节点node

情况 2：left和right只有一个不为 null

此时有两种子情况，但对代码来说处理方式完全一样：

子情况 A：最近公共祖先就在这个非 null 的子树里，现在还没走到那一步，需要把这个非 null 的值继续往上传递，让上层节点去判断
子情况 B：找到的就是p（或q）本身，另一个节点在它的子树下面，所以p（或q）自己就是最近公共祖先

不管是哪种子情况，处理方式都是：把非 null 的那个值往上返回

子情况A示例：最近祖先在子树深处，往上传递 3 / \ 5 null ← 5 子树里找到了 p、q，最近祖先是 5 / \ 6 2 ← 5 的 left=6 不为null，right=2 不为null → 5 是最近祖先 ← 3 的 left=5（返回的最近祖先），right=null → 把 5 往上传 子情况B示例：p 或 q 自己就是最近祖先 3 / \ 5 1 / \ 6 2 ← p=5, q=2，q 在 p 的子树里 ← 遍历到 5 时直接命中 p，返回 5 ← 3 的 left=5，right=null → 把 5 往上传，5 就是最近祖先

情况 3：left和right都为 null

说明左右子树都没找到p或q，当前节点的子树里没有目标，返回 null

returnleft!=null?left:right;// 如果 left 不为 null 返回 left，否则返回 right// left 和 right 都为 null 时，返回 right（也是 null）// left 和 right 只有一个不为 null 时，返回那个非 null 的// left 和 right 都不为 null 时，上面已经 return 了，走不到这里

这一行代码同时处理了情况 2 和情况 3，很简洁