题目描述
思路解析
一句话答案：LeetCode 865 具有所有最深节点的最小子树：一次后序遍历，每个节点回传子树高度和候选根，左右等深答案就是自己、否则跟更深那侧抬上去，时间 O(n)、空间 O(h)。
同时罩住所有最深节点的最小子树，找它的根
给一棵二叉树，每个节点的深度就是它到根走过的边数，深度最大的那些节点叫最深节点，可能不止一个。要返回同时包住全部最深节点的那棵最小子树的根——子树就是某个节点连同它下面的所有后代。题面例子 root=[30,50,15,60,20,85,90,null,null,70,45]，最深的是 70 和 45，答案是以 20 为根的子树 [20,70,45]。
先测全树深度再找根，来回两趟麻烦在哪
量出全树最深那层不难，一遍遍历就能拿到最大深度。可深度到手之后呢？最深的 70 和 45 分别挂在 20 的左右两边，散在树的不同角落，你还得再扫一遍把它们全找出来，再求它们的最近公共祖先，也就是两个节点最靠下的那个共同祖先。两遍遍历还要记下每个最深节点在哪，节点一多就容易记乱。
一次后序遍历，每个节点只回传两样东西
不必先测深度。换成后序遍历，也就是等左右两支各自算完了才轮到当前节点收口，让每个节点在回溯时只回传两样东西：这棵子树里包住所有最深节点的那个候选根，和这棵子树的高度。高度从叶子往上数，叶子算 1，每往上一层加 1。父节点手里一旦攥着左右两棵子树的高度，谁深谁浅一比就清楚了，答案在回溯途中就能往上递。
回溯到每个节点，比左右高度决定往上抛谁
每到一个节点，先递归拿到左子树的高度 ld、右子树的高度 rd，空节点的高度算 0。接着分三种情况：左边更深就说明最深节点全在左边，把左子树抬上来的候选根原样往上传、高度记成 ld+1；右边更深就传右子树的候选根、高度记成 rd+1；左右一样深这种情况——两侧各藏着同样深的最深节点，唯有当前这个节点能同时罩住它们，于是候选根就是当前节点自己、高度记成 ld+1。一路回溯到根，根拿到的那个候选根就是答案。
顺着题面这棵树，逐节点算一遍高度和候选根
底层叶子 60、70、45 先结算，叶子左右都是空、高度都是 0、正好相等，各自回传高度 1。到节点 20：左孩子 70 高度 1、右孩子 45 高度 1，一样深，按等深规则 20 自己当候选根、回传高度 2。到节点 50：左孩子 60 高度 1、右孩子那支高度 2，右边更深，把右边的候选根 20 原样抬上来、回传高度 3。右半边同理，叶子 85、90 各回传高度 1，节点 15 左右等深、回传候选根 15、高度 2。最后到根 30：左边高度 3、右边高度 2，左边更深，把左边一路抬上来的候选根 20 定成最终答案，以 20 为根的子树 [20,70,45] 恰好同时罩住 70 和 45。
等深必须留自己，别把高度和深度看成一回事
整棵树只走一遍后序遍历，每个节点回溯时做一次高度比较，时间 O(n)；额外空间是递归栈深度，等于树高 h，树退化成一条链时最坏是 O(n)。等深时若手一滑还往某一侧抛，答案就会偏向那半、漏掉另一侧的最深节点，等深时唯一正确的动作是留下当前节点自己。把回传的高度和题面的深度混为一谈同样会算错：深度从根往下量、越深越大，高度从叶子往上数、越往上越大，回传的自始至终是高度。还有个边界，全树只有一个最深节点时，它没有并列同深的另一半，答案就是这个节点自身的子树。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这句口诀：左右等深当前为答案，否则跟更深那一侧。下面每一帧都在套它。
准备 · 看清全树：这是一棵 9 个节点的二叉树，根是 30。我们要找包含全部最深节点的最小子树。最底层的 70 和 45 在深度 3（到根 3 条边），是全树最深的两个节点。直觉上，能同时罩住它们的最小子树，根就是它们的最近公共祖先。下面用一次后序 DFS 把这个结论严格算出来。
目标 · 最深节点：先把目标点亮：70 和 45 都在第 4 层（根算第 1 层，到根 3 条边、深度 3），是全树最深的节点。我们要的子树必须同时包含这两个，而且尽量小。带着这个目标开始后序遍历，注意我们全程不直接去测深度，而是靠每个节点比较左右子树的高度来推断。
下行 · 进入 30：下行进入节点 30。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 30。先去它的左孩子。
下行 · 进入 50：下行进入节点 50。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 50。先去它的左孩子。
下行 · 到达 60：沿当前路径下行，来到节点 60。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
结算 · 叶子 60：结算叶子 60：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，60 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 60。
下行 · 进入 20：下行进入节点 20。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 20。先去它的左孩子。
下行 · 到达 70：沿当前路径下行，来到节点 70。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
结算 · 叶子 70：结算叶子 70：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，70 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 70。
下行 · 到达 45：沿当前路径下行，来到节点 45。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
结算 · 叶子 45：结算叶子 45：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，45 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 45。
结算 · 20 等深：回到节点 20 结算。左子树高度 1，右子树高度 1，两边一样深。这说明 20 的左右两侧各藏着同样深的最深节点，唯一能同时罩住它们的最小子树，就是 20 自己。于是 20 升级为候选答案根，返回高度 2。
结算 · 50 跟右：回到节点 50 结算。左子树高度 1，右子树高度 2，右边更深。最深的节点全在更深那一侧，50 自己虽然能罩住所有最深节点，但会把浅的一侧也带进来，所以不是最小答案。把右侧抬上来的候选根 20 原样继续往上抛，高度更新为 3。
下行 · 进入 15：下行进入节点 15。它还有孩子，现在还不能结算，得先把左右两棵子树的高度都递归算出来，再回头处理 15。先去它的左孩子。
下行 · 到达 85：沿当前路径下行，来到节点 85。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
结算 · 叶子 85：结算叶子 85：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，85 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 85。
下行 · 到达 90：沿当前路径下行，来到节点 90。它没有左右孩子，是一个叶子。叶子下面是两个空，高度都按 0 算，马上结算它。
结算 · 叶子 90：结算叶子 90：左右都是空，两侧高度都是 0，正好相等。按口诀“等深则当前为答案”，90 自己就是这棵单节点子树里所有最深节点的最小子树。返回一对值：高度 1，候选根 90。
结算 · 15 等深：回到节点 15 结算。左子树高度 1，右子树高度 1，两边一样深。这说明 15 的左右两侧各藏着同样深的最深节点，唯一能同时罩住它们的最小子树，就是 15 自己。于是 15 升级为候选答案根，返回高度 2。
结算 · 30 跟左：回到节点 30 结算。左子树高度 3，右子树高度 2，左边更深。最深的节点全在更深那一侧，30 自己虽然能罩住所有最深节点，但会把浅的一侧也带进来，所以不是最小答案。把左侧抬上来的候选根 20 原样继续往上抛，高度更新为 4。
完成 · 答案子树：根 30 结算时，左边高度 3、右边高度 2，左边更深，于是把左边一路抬上来的候选根 20 定为最终答案。点亮的子树 20、70、45 恰好同时罩住两个最深节点 70 和 45，而且是满足条件里最小的一棵。答案就是以 20 为根的子树。
边界先想清：只有一个最深节点时，答案就是那个节点本身的子树。
面试重点：讲清为什么自底向上一遍就能同时算出高度和答案。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(root: Optional[TreeNode]) -> Tuple[Optional[TreeNode], int]: if root is None: return None, 0 l, ld = dfs(root.left) r, rd = dfs(root.right) if ld > rd: return l, ld + 1 if ld < rd: return r, rd + 1 return root, ld + 1 return dfs(root)[0]复杂度
- 时间：O(n)，一次后序遍历，每个节点只在回溯时做一次常数比较
- 空间：O(h)，递归栈深度等于树高 h，最坏(退化成链)为 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么一次后序 DFS 就够，不用先求全树最大深度再找？
追问这题和「最深叶子的最近公共祖先」是同一道吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
根据前序和后序遍历构造二叉树
LeetCode 889 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题