【LC 236】二叉树的最近公共祖先:为什么「命中即返回」就自动处理了「自己是祖先」
适用读者:会写二叉树递归遍历,但一看这题就觉得"边界太多、情况太杂"的人
技术栈:Python 为主,附 Java 版
难度:中等(代码 8 行,但每一行都在考你对递归返回值的理解)
收获:一个只问"子树里有没有"的后序 DFS,三种返回值的含义,以及 235 / 1650 / 1676 一整串变体
题目
给定一个二叉树,找到该树中两个指定节点的
最近公共祖先(Lowest Common Ancestor,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 的最近公共祖先是节点 5,因为根据定义最近公共祖先节点可以为节点本身。
这题是
二叉树递归的"毕业考"。它短,但短得很危险 —— 面试官从这一题能看出你三件事:
变体也成串:
出处备注:LC 236 是字节、腾讯、美团的递归高频题。被选中的原因很直接:8 行代码,但"返回值到底代表什么"这件事说不清楚的人占大多数。 面试官最爱追问的那句就是"如果 p 是 q 的祖先呢?"—— 本文第 3 节专门回答它。
节点的定义,沿用前几篇:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
输入格式提醒:[3,5,1,6,2,0,8,null,null,7,4] 同样是 LeetCode 的层序数组编码(和 LC 102 一样)。下标 i 的节点,左孩子在 2i+1、右孩子在 2i+2,空缺位置用 null 占位。这篇后面画的树就是按这个规则还原的 —— 注意 6 的两个孩子位是 null(它没有孩子),所以 [7,4] 挂在 2 下面,而不是挂在 6 下面。
一、先说清楚这题到底难在哪
1.1 直觉方案为什么不够好
最直白的想法是:
把 p 的祖先链和 q 的祖先链都求出来,然后从后往前找第一个公共的。
def lowestCommonAncestor(self, root, p, q):
path_p, path_q = [], []
def dfs(node, target, path): # 求从根到 target 的路径
if not node:
return False
path.append(node)
if node is target:
return True
if dfs(node.left, target, path) or dfs(node.right, target, path):
return True
path.pop() # 回溯:这条分支里没有
return False
dfs(root, p, path_p)
dfs(root, q, path_q)
# 两条路径从根开始逐位比较,最后一个相同的节点就是 LCA
i = 0
while i < len(path_p) and i < len(path_q) and path_p[i] is path_q[i]:
i += 1
return path_p[i - 1]
这个写法是对的,时间复杂度也是
O(n)。但有两个问题:
- 要遍历两遍(一遍找 p 的路径,一遍找 q 的路径),而且要用额外的
path 数组存两条链;
- 更关键的是,面试官会接着问:"能不能只遍历一遍、不用辅助数组?"
答案能,而且代码只有 8 行。这就是本文的主角。
1.2 换个角度:不问"路径",问"子树里有没有"
路径法的思路是"先定位两个目标,再比对祖先链"。递归法则把问题
下沉到每一个节点,问每个节点一个更朴素的问题:
站在你这个节点往下看,你的子树里能找到 p 和 q 吗?
对每个节点
node,可能的回答只有三种:
这第三种情况有个更精确的判据:
左右两边各回来一个非空,说明 p 和 q 分别在 node 的两侧子树里。 那
node 就是那个"分叉点",也就是最近的公共祖先。
而第 2 种情况是这题的精髓:
只找到一个的时候,返回的不是答案,而是一个"标记"。 它在说"我这边有一个,谁是另一个赶紧来找我汇合"。
这个区分是整题的钥匙。"返回值是答案"和"返回值是标记"是两件事,混在一起想就一定会绕晕。
1.3 "一个节点也可以是它自己的祖先"怎么办
题目特意加了这句定义,很多人第一反应是"哦,那要特判
p.parent is q 之类的情况"。
不需要。 这句话是靠下面这一行
自动处理的:
if not node or node is p or node is q:
return node
拆开看这行在做什么:
递归一旦走到 p(或 q),立刻返回 p 本身,不再往它的子树里走。
为什么这样就够了?两种可能都覆盖了:
- 如果 q 在 p 的子树里:dfs(p) 返回 p,这个 p 会一路往上冒。上面的祖先拿到"左边是 p"这个标记,再和右边的结果比 —— 而右边的子树里怎么样都不会再有 q 了(因为 q 在 p 底下,已经被 p 这一处返回截断了)。于是 p 一路冒到根,答案就是 p。自动正确;
- 如果 q 不在 p 的子树里:那 p 就只是个"标记",继续往上冒,直到某个节点发现"左右两边都非空",那个节点才是答案。
所以
这题不需要为"p 是 q 的祖先"单独写分支。那一行
return node 顺手就把这件事办了 —— 这是这题设计得最漂亮的地方。
二、动画:看着返回值一层层往上冒
下面这个动画把整个过程拆成 23 帧。我们要找的是
p = 6、q = 4 的 LCA(答案是
5)。
为什么不用官方第一例的 p = 5, q = 1?因为那组里 5 和 1 恰好是根的两个孩子,递归第二帧就命中、总共只有 8 帧,根本看不出"后序回溯"的味道。而 6 和 4 都埋在 5 的子树深处,能把"先钻到底、再一层层往上报"演完整。
画面分三块,看的时候分别盯:
- 左边的树:绿色实线是"子树里找到了东西"的节点,灰色虚线是"这棵子树白跑了"(返回
null)的节点。节点左上角的小标签是它向上报告的返回值。带红色圆环的是最终答案(分叉点);
- 中间的调用栈:栈底在下、栈顶在上。栈越往上涨说明递归钻得越深,栈往回收说明在回溯。每行还标了它"卡在哪个阶段"(刚进入 / 等右子树 / 等返回值 / 做判断);
- 底部的传送带:显示这一刻正在向上返回的值,以及它的身份 —— 是
p 的标记、q 的标记,还是已经确定的"答案本身"。
看动画时专门盯住三帧:
- 第 3 帧(
hit):进入 6,立刻命中,不再往下探(6 是叶子,看不出差别;换成 p = 5 时就能明显看到它的子树根本没被展开);
- 第 12 帧(
decide):5 发现左子树回来 6、右子树回来 4,左右都非空 → 分叉点 → 返回自己 5。这一帧是整题的转折点,传送带上第一次出现"答案本身";
- 第 21 帧(
decide):根 3 也同时是 p、q 的祖先,但它只有一个非空(左边冒上来的 5),所以它不是分叉点,只是路过 —— 把 5 继续往上冒。这就是"最近"两个字的实际体现。
三、完整推演表(23 帧逐帧)
用动画里的例子:
层序数组下标: 0=3 1=5 2=1 3=6 4=2 5=0 6=8 7=null 8=null 9=7 10=4
树:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
p = 6,q = 4,答案 = 5
几个值得停下来看的地方:
① 第 3 帧的"不下探"。 进入
6 立刻返回。如果
q 恰好藏在
6 的子树里,那
6 就该直接当答案 —— 这就是"自己是自己的祖先"。这里
q 不在,所以
6 只是个标记。
② 第 12 帧的"分叉点"。 5 左边回来
6(p 的标记),右边回来
4(q 的标记)——
左右都非空,全树唯一一次。所以
5 就是答案。
③ 第 21 帧的"路过"。 根
3 也同时是 p 和 q 的祖先,但它的左边是
5(非空)、右边是
null(空)—— 只有一个非空,说明
两个目标都在同一侧。所以
3 不是分叉点,只是把
5 继续往上冒。
这正是"最近"的判据:不是"同时包含",而是"左右分居两侧"。
顺带看第 19 帧:整棵以 1 为根的右子树跑完,返回 null。递归并没有提前退出 —— 它老老实实把整棵树都走了一遍。这题的 O(n) 就是这么来的,没有任何剪枝(因为你不走完就不知道另一侧有没有目标)。
四、完整代码
4.1 Python 版(8 行主逻辑)
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
# base case 1:空节点
# base case 2:命中 p 或 q —— 立刻返回,不再下探子树
# ("一个节点也可以是它自己的祖先"就靠这一行)
if not root or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q) # 左子树找到了啥
right = self.lowestCommonAncestor(root.right, p, q) # 右子树找到了啥
if left and right:
return root # ★ 左右都非空 = 两个目标分居两侧 = root 就是 LCA
return left or right # ★ 只有一个非空就如实上报(可能两个都空 → 返回 None)
就这 8 行。 但每一行都在承载信息,下面逐个说。
4.2 逐行拆解
if not root or root is p or root is q: return root
三个条件合并在一个
if 里,返回的都是
root(空的时候是
None):
not root:走到空节点,什么都没找到,返回 None;
root is p or root is q:命中!立刻返回自己,不再往下探。
⚠️ 这里用的是 is 而不是 ==。is 比较的是对象身份(是不是同一个节点对象),== 比较的是值。如果树里有重复的值(比如两个节点都是 5),用 == 就会把"值等于 5"的节点当成 p,直接错。树类题目里判断"是不是同一个节点"一律用 is。
left = dfs(root.left) 和 right = dfs(root.right)
注意顺序:这两行是"先递归、后判断"。 也就是说,站在
root 视角,它
必须等信息从下面回来才能做决定 —— 这就是
后序遍历的特征(先处理子节点,再处理自己)。
left /
right 的值就是子树向上汇报的结果,含义见第 1.2 节的三种情况。
if left and right: return root
这是
唯一的"报答案"分支。
left 和
right 都是节点对象(非
None)时,说明:
- 左子树里有 p 或 q 之一;
- 右子树里也有 p 或 q 之一;
- 两边各一个 → p 和 q 在
root 这里分叉了 → root 就是最近公共祖先。
为什么"最近"? 因为递归是自底向上的,第一个发现"左右都非空"的节点(也就是
深度最大的那个)就会立刻返回自己。再往上的祖先虽然也同时包含 p 和 q,但它们不是第一个发现的 —— 而
root 这个答案会继续向上冒,途中所有的祖先都走"只有一个非空"的分支,
不会覆盖它。
return left or right
这行同时覆盖两种剩余情况,靠的是 Python 的
or 短路:
- 只有一个非空(比如
left 是节点、right 是 None):返回那个非空的。含义是"两个目标都在这一侧,我如实上报";
- 两个都空:
left or right 是 None,返回 None。含义是"这棵子树里一个都没有"。
left or right 是这题的精简写法。写全了是这样的:
python
if left and right:
return root
elif left:
return left
else:
return right # right 可能是节点,也可能是 None
效果完全一样。or 写法少三行,但面试时建议先写全,确认逻辑后再简化 —— 因为 left or right 有个前提:left、right 只可能是"节点对象"或 None,不会有别的假值。(Python 里 TreeNode 对象没有定义 __bool__ / __len__,所以它恒为真。这一点成立,or 才安全。)
4.3 复杂度
- 时间
O(n):每个节点恰好被访问一次(dfs 对每个节点只调用一次)。注意没有任何剪枝 —— 就算在左子树就找到了分叉点,右子树也照样要跑完,因为得知道"另一侧到底有没有目标";
- 空间
O(h):递归栈的深度等于树高。最坏情况(完全偏斜的树)退化成 O(n),平衡树是 O(log n)。
和路径法对比:路径法时间也是 O(n)(两遍),但空间要额外存两条 O(h) 的路径数组,而且是两遍遍历。递归法一遍搞定、除递归栈外零额外空间。这是它更优的地方。
五、变体一:LC 235 二叉搜索树的最近公共祖先
要求:树换成
BST,找 p、q 的 LCA。
5.1 BST 的有序性让"回溯"整个消失了
BST 有个关键性质:
左子树的值全都小于根,右子树的值全都大于根。
于是站在任何一个节点看 p 和 q 的值,只有三种情况:
第三种情况和 LC 236 的判据是同一个道理("分居两侧 = 分叉点"),但实现完全不同:
- LC 236 必须后序(先钻到底,靠子树返回值判断)—— 因为它不知道 p、q 在哪,只能搜遍全树;
- LC 235 不需要后序,也不需要返回值冒泡 —— 它在当前节点就能直接判断该往哪走,是前序的、一次走一条路。
5.2 代码
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
while root:
if p.val < root.val and q.val < root.val:
root = root.left # 两边都小 → 一起往左
elif p.val > root.val and q.val > root.val:
root = root.right # 两边都大 → 一起往右
else:
return root # 分叉了(或其中一个就是 root)
return None
没有递归、没有栈、没有回溯。 空间
O(1)(迭代版),时间
O(h)。
注意 else 分支同时覆盖了"一个左一个右"和"p.val == root.val(或 q.val)"。后者就是"自己是自己的祖先"在 BST 版里的体现 —— 当 p 正好是当前节点时,p.val < root.val 和 p.val > root.val 都不成立,自然落到 else 返回 root。又是自动处理的,不用特判。
递归版(更接近 236 的写法,但同样不需要左右都递归):
def lowestCommonAncestor(self, root, p, q):
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root
⚠️ 面试高频追问:"235 能不能直接用 236 的代码?" —— 能跑对,但浪费了 BST 的性质:236 是 O(n),235 的最优解是 O(h)。面试官问 235 就是想看你有没有用上"有序"这个条件,直接套 236 等于主动放弃了 O(n) → O(h) 的优化。
5.3 两者的对照
一句话记住区别:236 只能"搜",235 可以"判"。
六、变体二:LC 1650 带父指针的最近公共祖先
要求:节点结构多了一个
parent 指针,仍然求 p、q 的 LCA。
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None # ★ 多了这个
6.1 本质是"两条链表求交点"
有了
parent 指针,从 p 出发沿着
parent 往上走,能得到一条
从 p 到根的链;q 同理。
最近公共祖先就是这两条链的第一个交点。
这和 LC 160 相交链表(本系列第 8 篇)是同一道题:两条链长度不同,找第一个公共节点。
6.2 代码:复用相交链表的手法
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
a, b = p, q
while a is not b:
# 走到头就换到另一条链的起点,两次遍历后长度差被抹平
a = a.parent if a.parent else q
b = b.parent if b.parent else p
return a
完全就是 LC 160 的双指针解法。 也可以先求两条链的长度差、让长的先走几步(也是 160 的另一个常见解法)。
用集合的写法更直白:
def lowestCommonAncestor(self, p, q):
seen = set()
while p:
seen.add(p)
p = p.parent
while q not in seen:
q = q.parent
return q
6.3 和 236 的关系
关键对比:1650 之所以能 O(1) 空间,是因为 parent 指针把"往上走"这件事变成了显式操作。236 里没有这个指针,"往上"只能靠递归返回值一层层传 —— 这就是为什么 236 必须有"返回值冒泡"这个机制。
七、再顺手带两个
7.1 LC 1676 多目标 LCA:目标是"全部找到"
要求:给一个节点数组
nodes,求它们
全部的最近公共祖先。
把 236 的"左右都非空"推广成"
计数器":
class Solution:
def lowestCommonAncestor(self, root, nodes):
target = set(nodes) # 用集合,O(1) 判断
def dfs(node):
if not node:
return None
if node in target: # 命中任一目标 → 立刻返回(同 236 的命中即返回)
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
return node # 左右都有目标 → 分叉点
return left or right
return dfs(root)
和 236 唯一的区别是 node is p or node is q 换成了 node in target。 整个骨架一字未改 —— 这也说明 236 的核心机制(返回值冒泡 + 分叉点判据)本身就和"几个目标"无关。
注意这里有个前提:多个目标分居左右两侧时,left and right 就成立。但如果所有目标都在同一侧,那答案就是那一侧的返回值。逻辑天然成立。
7.2 LC 1123 最深叶节点的 LCA:目标是"最深的那些"
要求:返回
最深层叶子节点的最近公共祖先。
这题变成了
带深度信息的后序:
class Solution:
def lcaDeepestLeaves(self, root):
def dfs(node):
if not node:
return (0, None) # (深度, 该子树最深叶子的 LCA)
dl, nl = dfs(node.left)
dr, nr = dfs(node.right)
if dl > dr:
return (dl + 1, nl) # 最深叶子只在左边
if dr > dl:
return (dr + 1, nr) # 只在右边
return (dl + 1, node) # 两边一样深 → 分叉点就是 node
return dfs(root)[1]
又是"分叉点"这个模式:左右两边的深度相等时,
node 就是答案。
三题共用同一个骨架:"后序 + 把子树的结论向上汇报 + 在某个条件下判定自己是答案"。
八、Java 版
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; // 如实上报
}
}
Java 里两个提醒:
root == p 是引用比较,和 Python 的 is 对应。同样不要写成 root.val == p.val —— 有重复值时直接错;
- 返回值不能是
null 的语义混淆:Java 里 null 同时表示"这棵子树没有目标",而 p/q 本身也永远不可能是 null(题目保证),所以 left != null 这个判断是安全的。
BST 版(迭代,
O(1) 空间):
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
return root; // 分叉了,或其中一个就是 root
}
}
return null;
}
}
九、边界情况
三个容易错的:
1. 忘记处理"p 是 q 的祖先"。 这是本题最经典的失分点。
不需要特殊处理 ——
if root is p or root is q: return root 那一行已经自动覆盖了(见第 1.3 节)。
2. 用 == 而不是 is(Java 里用 == 比较对象)。
if not root or root.val == p.val or root.val == q.val: # ✗ 有重复值时错
树里允许重复值,
val 相等不代表是同一个节点。必须比身份。
3. 以为"找到一个目标就能提前返回"。
如果 p 和 q 分别在根的两侧,那你在左子树找到 p 之后,
仍然必须把右子树跑完才知道 q 在不在那边。
这题没有任何剪枝空间,
O(n) 是下界。
例外情况:如果题目额外保证"p、q 一定在树里"(本题就是这样),理论上可以在找到两个目标后提前结束,但那样要引入全局状态(计数器 + 提前退出标记),代码会复杂得多,而且面试官一般期待的是那个 8 行干净版本。别为了这点常数优化把代码写乱。
十、常见坑
1. 把"返回值是标记"当成"返回值是答案"。
这是最核心的认知坑。当
dfs(某节点) 返回
p 时,
它只说"我这边有 p",不代表这个 p 就是 LCA。真正的答案只有
if left and right 那一支才产生。
写代码时如果脑子里把两者混为一谈,就会出现"一找到 p 就直接 return p 当答案"这类错误(在 p、q 分居两侧时直接错)。
2. 用 root.val 比较而不是 root is p。
见上一节第 2 点。
重复值用例专门用来抓这个。
3. 写成"左边没找到就直接返回右边",漏掉等左边。
left = self.lowestCommonAncestor(root.left, p, q)
if not left:
return self.lowestCommonAncestor(root.right, p, q) # ✗ 少了"两边都非空"的判断
两棵子树必须都跑完,因为分叉点的判据恰恰是"左右都非空"。必须先把两个结果都拿到手,再判断。
4. BST 版套用 236 的代码。
能过,但
放弃了 BST 的有序性,
O(h) 变
O(n)。面试官会追问"能不能更快"。
5. 递归里用全局变量存"找到的第一个目标"。
有些解法用一个
found 变量记录"已经找到了一个目标",找到第二个时就返回 ——
这需要额外处理"第一个目标的祖先链",比标准写法复杂且容易错。
标准解不需要任何全局状态。
6. Java 里返回 null 的两重含义没分清。
Java 里
null 既表示"子树里没找到",又用来表示"空节点"。因为
p、
q 保证非
null,所以两者不会冲突 —— 但
心里要清楚这个前提,题目变了(比如允许 p 为
null)就不成立了。
十一、面试怎么答
开口 30 秒给思路(别一上来就写代码):
用后序 DFS。每个节点向上汇报"我的子树里找到了什么",返回值有三种含义:null 表示一个都没找到;返回 p 或 q 本身表示只找到一个(这只是个标记,不是答案);返回自己表示我就是分叉点。判据是:如果左右子树返回的值都非空,说明 p、q 分居两侧,当前节点就是最近公共祖先。base case 有两个 —— 空节点返回 null,命中 p 或 q 就直接返回自己、不再下探,这一行顺便就把"一个节点也可以是它自己的祖先"处理掉了。时间 O(n),空间 O(h)。
然后主动交代变体:
- BST 版(235):利用有序性,
p.val 和 q.val 都小就往左、都大就往右、否则当前节点就是答案。从前序一次走一条路,O(h)。不用回溯;
- 带 parent(1650):本质是两条链表求交点,和 160 一样用双指针,
O(1) 空间。
追问应对:
- "如果 p 是 q 的祖先呢?" —— 自动处理了。递归走到 p 就命中返回 p,不会再往它的子树走;p 一路冒到根,所有祖先都走"只有一个非空"的分支,不会覆盖它。所以答案是 p 本身,符合"自己是自己的祖先"的定义。不需要额外分支。
- "为什么要用
is 不用 ==?" —— 树里可以有重复值。== 比较值会把"值相同但不同节点"误认成目标。is 比较对象身份,才是正确的。
- "能不能提前返回省点时间?" —— 不能有效剪枝。p、q 分居两侧时,必须把右子树跑完才知道 q 在不在。找到分叉点之后确实可以不继续往上(因为答案已经确定),但代价是引入全局状态,代码变复杂,不划算。
- "为什么是后序遍历?" —— 因为判断"我是不是分叉点"需要先知道左右子树的情况。信息从下往上流,所以必须后序。
- "空间为什么是 O(h)?" —— 递归栈深度等于树高。平衡树
O(log n),完全偏斜树退化成 O(n)。
- "最小的 LCA、最大的 LCA 怎么求?" —— 稍微跑题但常被带出来:BST 里就是"最左叶子和最右叶子的 LCA",即根(如果不是 BST,就用 236 的通用解)。
- "235 和 236 能统一吗?" —— 判据是同一个("分居两侧"),但 236 只能靠子树返回值搜出来,235 能靠值的大小直接判断。统一的是思想,不是代码。
结语
把树系列的递归题串起来看,这题的位置是这样的:
这题值得带走的不是那 8 行代码,而是这个反射:
看到"两个节点的关系"要自底向上判断,就先想后序;看到"子树里的信息要传给父亲",就把返回值当成一个可以承载多重含义的载体。
236 / 235 / 1650 / 1676 / 1123 五道题,
判据全是"分叉点":左右两侧各有一个目标,当前节点就是答案。
- 236:左右子树的返回值都非空;
- 235:p、q 的值分居
root.val 两侧;
- 1650:两条向上链的第一个交点;
- 1676:左右子树都有目标;
- 1123:左右子树的深度相等。
记住"分叉点"这个形状,剩下的是换判据;记不住它,每一道都得重新想一遍"最近"是什么意思。
dfs(node)
├─ 空 / 命中 → 立刻返回(不再下探)
├─ left = dfs(node.left) ← 先把左子树的结论拿到手
├─ right = dfs(node.right) ← 再把右子树的结论拿到手
└─ 左右都非空 ? 返回自己 : 如实上报
↑
全树唯一的一次"分叉",就是答案
返回值是信使,不是答案。 只有当左右两个信使同时回来的时候,接收它们的那个节点才成为答案。