题目描述
思路解析动画文字版
记牢这一句:先递归到最底下,再一层层往上把和与个数带回来,在每个节点顺手算一次平均、比一次值。下面从根出发,一路下探到叶子,再自底向上回算。
准备 · 后序遍历,先探到底再回算：先看清这棵树的形状。后序遍历的规矩是:不急着在半路结算,而是一头扎到最底下的叶子,从叶子开始把子树的和与个数一层层往上抬。你盯住紫色,它代表当前正在处理的节点;绿色代表已经验过、达标的节点;红色代表验过但不达标的节点。现在从根出发往下走。
约定 · 空节点返回(和 0,个数 0)：正式下探前先说好一个约定:走到空位置,也就是没有节点的地方,直接返回和 0、个数 0,它什么都不贡献。有了这条,叶子的左右孩子都是空,回来都是 0 加 0,叶子的子树和就只剩它自己,个数就是 1,天然成立。这条约定是整个递归能自底向上算对的地基。
下行 · 进入值 54 的节点：走到值 54 的节点,它下面还挂着孩子,现在还不能结算。按后序的规矩,得先把它的左子树整个算完、右子树整个算完,拿到两边的和与个数,才轮到它自己。先钻左子树。
下行 · 进入值 40 的节点：走到值 40 的节点,它下面还挂着孩子,现在还不能结算。按后序的规矩,得先把它的左子树整个算完、右子树整个算完,拿到两边的和与个数,才轮到它自己。先钻左子树。
下行 · 进入值 30 的节点：走到值 30 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 30,个数是 1。下一帧直接给它结算。
结算 · 叶子值 30 达标：结算值 30 的这个叶子。子树只有它自己,和是 30,个数是 1,平均就是 30 除以 1 等于 30。这个平均正好等于节点自己的值 30,达标,把它标绿,达标节点数变成 1。它向上返回的就是一对数字:和 30、个数 1。
回到值 40 · 转向右孩子：值 40 的左子树整个算完了,左边带回来的是:和 30、个数 1。但现在还不能拍板,右子树还没碰。回到值 40,接着钻它的右子树,把右边那对数字也拿回来。
下行 · 进入值 51 的节点：走到值 51 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 51,个数是 1。下一帧直接给它结算。
结算 · 叶子值 51 达标：结算值 51 的这个叶子。子树只有它自己,和是 51,个数是 1,平均就是 51 除以 1 等于 51。这个平均正好等于节点自己的值 51,达标,把它标绿,达标节点数变成 2。它向上返回的就是一对数字:和 51、个数 1。
汇总 · 值 40 合并左右子树：左右子树都回来了。值 40 把两边的和加上自己的值:30 加 51 加 40,等于 121;个数是左边 1 加右边 1 再加自己这一个,等于 3。这就是值 40 整棵子树的和与个数,下一帧拿它算平均。
结算 · 值 40 达标：给值 40 结算。平均值等于和 121 除以个数 3。算出来是 40.33,向下取整拿 40。这个 40 恰好等于节点自己的值 40,达标,标绿,达标节点数变成 3。不管达不达标,它都要照常把和 121、个数 3 向上返回给父节点。
回到值 54 · 转向右孩子：值 54 的左子树整个算完了,左边带回来的是:和 121、个数 3。但现在还不能拍板,右子树还没碰。回到值 54,接着钻它的右子树,把右边那对数字也拿回来。
下行 · 进入值 88 的节点：走到值 88 的节点,它下面还挂着孩子,现在还不能结算。按后序的规矩,得先把它的左子树整个算完、右子树整个算完,拿到两边的和与个数,才轮到它自己。先钻左子树。
下行 · 进入值 25 的节点：走到值 25 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 25,个数是 1。下一帧直接给它结算。
结算 · 叶子值 25 达标：结算值 25 的这个叶子。子树只有它自己,和是 25,个数是 1,平均就是 25 除以 1 等于 25。这个平均正好等于节点自己的值 25,达标,把它标绿,达标节点数变成 4。它向上返回的就是一对数字:和 25、个数 1。
回到值 88 · 转向右孩子：值 88 的左子树整个算完了,左边带回来的是:和 25、个数 1。但现在还不能拍板,右子树还没碰。回到值 88,接着钻它的右子树,把右边那对数字也拿回来。
下行 · 进入值 95 的节点：走到值 95 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 95,个数是 1。下一帧直接给它结算。
结算 · 叶子值 95 达标：结算值 95 的这个叶子。子树只有它自己,和是 95,个数是 1,平均就是 95 除以 1 等于 95。这个平均正好等于节点自己的值 95,达标,把它标绿,达标节点数变成 5。它向上返回的就是一对数字:和 95、个数 1。
汇总 · 值 88 合并左右子树：左右子树都回来了。值 88 把两边的和加上自己的值:25 加 95 加 88,等于 208;个数是左边 1 加右边 1 再加自己这一个,等于 3。这就是值 88 整棵子树的和与个数,下一帧拿它算平均。
结算 · 值 88 不达标：给值 88 结算。平均值等于和 208 除以个数 3。算出来是 69.33,向下取整拿 69。这个 69 并不等于节点自己的值 88,不达标,标红,达标节点数不加,仍是 5。不管达不达标,它都要照常把和 208、个数 3 向上返回给父节点。
汇总 · 值 54 合并左右子树：左右子树都回来了。值 54 把两边的和加上自己的值:121 加 208 加 54,等于 383;个数是左边 3 加右边 3 再加自己这一个,等于 7。这就是值 54 整棵子树的和与个数,下一帧拿它算平均。
结算 · 值 54 达标：给值 54 结算。平均值等于和 383 除以个数 7。算出来是 54.71,向下取整拿 54。这个 54 恰好等于节点自己的值 54,达标,标绿,达标节点数变成 6。不管达不达标,它都要照常把和 383、个数 7 向上返回给父节点。
回放 · 6 个节点达标,答案 6：整棵树验完了。四个叶子 30、51、25、95 各自子树只有自己,平均等于自己,全达标;值 40 的子树平均 40、值 54 的子树平均 54,也都对得上,达标;唯独值 88 的子树平均是 69,不等于 88,不达标,标红。数一数绿色节点,一共 6 个,这就是答案。判定始终只做一件事:在每个节点算子树平均、和它自己的值比一比。
边界想清:单节点必达标;向下取整可能让 11 除以 2 变 5 恰好命中;全 0 树里每个节点都达标。
面试重点:后序返回(和,个数)自底向上、平均向下取整比值、时间 O(n) 空间 O(h)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator 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 = nextclass Solution: def averageOfSubtree(self, root: TreeNode) -> int: def dfs(root) -> tuple: if not root: return 0, 0 ls, ln = dfs(root.left) rs, rn = dfs(root.right) s = ls + rs + root.val n = ln + rn + 1 nonlocal ans ans += int(s // n == root.val) return s, n ans = 0 dfs(root) return ans复杂度
- 时间：O(n)，n 是节点总数。每个节点被后序 DFS 恰好访问一次,在节点处做的加法、一次除法、一次比较都是常数操作,总量随节点数线性增长
- 空间：O(h)，按峰值算,h 是树高。不额外开表,只有递归栈,栈深最多等于从根到最深叶子的层数 h。最坏是退化成链的树,h 达到 n;平衡树时 h 约为 log n
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么不能自顶向下做?
追问为什么时间是 O(n),空间是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
感染二叉树需要的总时间
LeetCode 2385 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题