题目描述
思路解析动画文字版
记牢这句口诀：左右等深当前为答案，否则跟更深那一侧。下面每一帧都在套它。
准备 · 看清全树：这是一棵 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题