题目描述
思路解析
一句话答案：LeetCode 2265 统计值等于子树平均值的节点数：一趟后序遍历自底向上，让每个节点带回子树的和与个数，就地把和整除个数得平均再比值，子树结果只算一次不重复遍历，时间 O(n)。
一个节点达标，是它的值恰好等于自己子树的平均
给一棵二叉树 root，每个节点带一个整数值。对任意节点，把它自己和它下面所有后代圈成一棵子树，子树所有值之和除以节点个数、再向下取整（往小舍），就是子树平均值。要数：整棵树里有多少个节点，值恰好等于自己子树的平均。题面例子 root=[54,40,88,30,51,25,95] 答案 6，单节点 root=[1] 答案 1。
要判一个节点，先得拿到它整棵子树的和与个数
判断一个节点达不达标，绕不开两个数：子树的值总和、节点个数，有它俩才除得出平均。照字面写就是对每个节点现场把整棵子树重走一遍求和数个数。可这样根节点扫全树、根的孩子又各扫半棵，越靠上重复扫得越多，节点数到 1000 时滚成 O(n²)，白算一堆本可复用的和。
一趟后序遍历，让子树的和与个数只算一次
父节点算平均时，子节点刚把子树走完，结果却丢掉又从头来。后序遍历省下这笔：等左右两棵子树把各自的和与个数都算好递上来，才轮到当前节点结算。这时左右子树数据早已备好，把两边的和加自己值、个数加 1，就得子树的和与个数，不必再往下钻。子树结果自底向上只传一次、被父亲复用，全树只走一遍。
每个节点向上返回一对数字：子树和与节点数
写成递归函数 dfs，对每个节点返回一对数字：子树的和 s、节点个数 n。递归的底是空位置：走到没节点处返回 0、0，什么都不贡献，叶子的和只剩自己、个数为 1。对真实节点，先递归左孩子拿到 (ls, ln)、右孩子拿到 (rs, rn)，然后 s = ls + rs + 当前值、n = ln + rn + 1。就地看 s 整除 n 是否等于节点值，整除即整数除法、余数扔掉，等于就把答案加一，再把 (s, n) 返回父亲。
题面这棵树，从叶子往上逐节点结算
后序先探到最底层。四个叶子 30、51、25、95 子树只有自己，和是自身、个数是 1，平均等于自身，全达标。
轮到值 40：左孩子 (30,1)、右孩子 (51,1)，s=30+51+40=121、n=3，121 整除 3 得 40，等于 40，达标，返回 (121,3)。值 88：左孩子 (25,1)、右孩子 (95,1)，s=25+95+88=208、n=3，208 整除 3 得 69，不等于 88，不达标，返回 (208,3)。
回到根 54：s=121+208+54=383、n=3+3+1=7，383 整除 7 得 54（54.71 向下取整），等于 54，达标。四个叶子加 40、54 共 6 个达标，答案 6。
分母撑错、或把平均当浮点比，答案就偏了
错一处结果就整体走样。空位置必须返回个数 0，按 1 算会撑大分母、平均偏小，达标节点漏判。比平均得用整数除法向下取整，用浮点数除，54.71 永远等不上 54，达标的全被判掉。和与个数缺一不可，只返和不返个数，父亲就数不出分母。
复杂度：每个节点在后序里只处理一次，节点内加法、除法、比较都是常数，时间 O(n)；额外只有递归栈，栈深等于树高 h，空间 O(h)。边界：单节点必达标；全 0 的树里每个节点平均都是 0，全达标。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:先递归到最底下,再一层层往上把和与个数带回来,在每个节点顺手算一次平均、比一次值。下面从根出发,一路下探到叶子,再自底向上回算。
准备 · 后序遍历,先探到底再回算：先看清这棵树的形状。后序遍历的规矩是:不急着在半路结算,而是一头扎到最底下的叶子,从叶子开始把子树的和与个数一层层往上抬。你盯住紫色,它代表当前正在处理的节点;绿色代表已经验过、达标的节点;红色代表验过但不达标的节点。现在从根出发往下走。
约定 · 空节点返回(和 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题