本文概览：本文以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，很简洁

第四步：完整执行过程

以这棵树为例：

3 / \ 5 1 / \ \ 6 2 8

下面用三个例子分别演示三种情况。核心要盯住每个节点递归后拿到的left和right——左右子树返回了什么，决定了当前节点怎么处理

例1：p = 5，q = 1（p、q 分别在根的左右两侧）

初始：从根节点 3 开始

访问节点 3（当前路径：3）

• 不是 p 也不是 q，递归左右子树

访问节点 5（当前路径：3→5）

• 命中 p=5，直接返回 5，不再往下递归
• → left = 5

访问节点 1（当前路径：3→1）

• 命中 q=1，直接返回 1，不再往下递归
• → right = 1

回到节点 3：left=5 不为 null，right=1 不为 null → 3 就是最近公共祖先，返回 3

结果：最近公共祖先是 3

例2：p = 5，q = 2（q 在 p 的子树里）

访问节点 3（当前路径：3）

• 不是 p 也不是 q，递归左右子树

访问节点 5（当前路径：3→5）

• 命中 p=5，直接返回 5，不再往下递归（2 虽然在 5 的子树里，但命中后不往下找）
• → left = 5

访问节点 1（当前路径：3→1）

• 不是 p 也不是 q，递归左右子树

访问节点 null（1 的左子树）

• 空节点，返回 null
• → left = null

访问节点 8（当前路径：3→1→8）

• 不是 p 也不是 q，左右子树都是 null，返回 null
• → right = null

回到节点 1：left=null，right=null → 返回 null

回到节点 3：left=5 不为 null，right=null → 把 5 往上传，返回 5

结果：最近公共祖先是 5（q=2 在 p=5 的子树里，p 自己就是最近祖先）

例3：p = 6，q = 2（都在左子树，最近祖先在深处）

访问节点 3（当前路径：3）

• 不是 p 也不是 q，递归左右子树

访问节点 5（当前路径：3→5）

• 不是 p 也不是 q，递归左右子树

访问节点 6（当前路径：3→5→6）

• 命中 p=6，直接返回 6
• → left = 6

访问节点 2（当前路径：3→5→2）

• 命中 q=2，直接返回 2
• → right = 2

回到节点 5：left=6 不为 null，right=2 不为 null → 5 就是最近公共祖先，返回 5

• → 节点 3 的 left = 5

访问节点 1（当前路径：3→1）

• 不是 p 也不是 q，递归左右子树
• 左子树 null，右子树 8 也不是 p、q → left=null，right=null → 返回 null
• → 节点 3 的 right = null

回到节点 3：left=5 不为 null，right=null → 把 5 往上传，返回 5

结果：最近公共祖先是 5（6 和 2 分别在 5 的左右两侧）

三个例子的共性：

• 例1：左右子树都返回非 null → 当前节点就是最近祖先
• 例2、例3：只有一边返回非 null → 把这个非 null 的值往上传递，最终传到根节点的就是答案

不管最近祖先在哪个位置，它一定是"第一次出现 left 和 right 都不为 null"的那个节点，找到后就会一路被往上传

第五步：回溯汇总的本质

整个过程其实就是回溯汇总：每个节点把左右子树的查找结果汇总到一起，做一次判断，然后把结果往上传

• 左右都找到了 → 当前节点就是最近祖先，把自己往上返回
• 只有一边找到了 → 把那一边的结果往上返回，让上层继续判断
• 两边都没找到 → 返回 null，告诉上层这里没有

最终结果会一层一层传递回根节点，根节点拿到的就是最终答案

这种"后序遍历先拿到子树结果，再在当前节点汇总"的模式，是二叉树问题中很常见的一种思路，适用于需要综合左右子树信息来做判断的场景

复杂度分析

• 时间复杂度：O(n)，每个节点最多遍历一次
• 空间复杂度：O(h)，递归栈深度等于树的高度，最坏情况 O(n)