题目描述
思路解析
一句话答案：LeetCode 508 出现次数最多的子树元素和：父节点的和依赖孩子，用后序遍历给每个节点算出子树和、边算边用哈希表计数，最后挑出现次数最多的那些和返回，时间 O(n)。
每个子树都有一个和，要数哪个和最常见
给一棵二叉树，每个节点都能框出一棵以它为根的子树；把这棵子树里所有节点值加起来，就是这个节点的子树和。叶子也算一棵子树，它的和就是自身那个值。全树 n 个节点凑出 n 个子树和，其中难免有重复。题目问的是：哪些子树和出现的次数最多，把它们全都返回，顺序不限。题面例子 root=[5,2,-3]，三个节点各给一个和，答案是 [2,-3,4]。
对每个节点各扫一遍子树求和，n 大了就吃力
求一个节点的子树和，得把它底下整棵子树都加一遍。可要是每个节点都各自这么加一次，靠上的节点会重复走下面一大片：根节点扫全树、根的两个孩子又各扫自己那半，同一个叶子被反复加进它每一个祖先的和里。n 个节点最坏叠到 O(n²) 量级的重复遍历，节点一多就慢得明显。
父亲的和等着孩子先算出来
重复全出在一件事上：父节点的和，等于它自己的值，加左子树的和，再加右子树的和。也就是说孩子的子树和只要算一次，父亲拿来直接用就行，用不着重新下去扫一遍。这就要求处理顺序是先孩子后父亲——两个孩子的和都递归求出来了，父节点才拿着它们把自己这棵子树的和拼起来，这种走法叫后序遍历。每个节点只在轮到自己时被加一次，重复就没了。
递归返回子树和，哈希表边算边记一笔
让递归函数 dfs 干两件事：算出当前节点的子树和 s = 节点值 + dfs(左) + dfs(右)，并把 s 返回给父亲；同时在一张按值计数的哈希表 cnt 里给 s 记一笔，也就是 cnt[s] 加一。空节点返回 0，正好当作递归到底的边界。
整棵树跑完，cnt 里存的就是每个子树和各出现了几次。取其中最大的次数 best，再把所有出现次数正好等于 best 的和收集起来，就是答案。这里要当心可能有好几个和并列 best，得一个不落全返回。
拿题面的 root=[5,2,-3] 从叶子算到根
这棵树三个节点：根 5，左孩子 2，右孩子 -3，两个孩子都是叶子。后序先下到左孩子 2，它没有孩子，dfs(左)、dfs(右) 都返回 0，子树和 s = 2 + 0 + 0 = 2，cnt[2] 记 1。再到右孩子 -3，同样是叶子，s = -3，cnt[-3] 记 1。最后回到根 5，它的和 s = 5 + 2 + (-3) = 4，cnt[4] 记 1。三个和 2、-3、4 各出现 1 次，最大次数 best = 1，于是三个都是答案，顺序不限，题面给的就是 [2,-3,4]。
写成前序就全错，还有两个必踩的坑
最致命的是遍历顺序：把后序写成前序或层序，父亲还没拿到孩子的和就抢先结算，得到的全是错值。另一个坑是只返回出现次数最多的那一个和——本题并列第一很常见，漏掉几个直接判错。还有别忘了叶子也是一棵子树，它的和就是自身，同样要记进 cnt，少记这一笔次数就可能数偏。
复杂度上，后序把每个节点访问、结算恰好一次，记哈希和最后扫表都是均摊 O(1)，时间 O(n)。空间看两处：哈希表最多存 n 个不同的和，递归栈深等于树高，链状树最坏也到 O(n)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条主线：先下钻到叶子，再自底向上结算每个子树和，边算边往哈希表记一笔。
准备 · 从根开始后序遍历：开局哈希表是空的。后序 DFS 从根节点 50 出发，先一路下钻到最左下的叶子，再自底向上一个个结算子树和。盯住右边这张计数表，它会随着结算逐行长出来。
下钻 · 进入 50：递归进入节点 50（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
下钻 · 进入 20：递归进入节点 20（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
下钻 · 进入 30：递归进入节点 30（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
下钻 · 到叶子 10：递归走到节点 10（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
结算 · 10 的子树和 10：节点 10 的左右子树和都齐了，结算：子树和 = 10。把 10 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
下钻 · 到叶子 40：递归走到节点 40（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
结算 · 40 的子树和 40：节点 40 的左右子树和都齐了，结算：子树和 = 40。把 40 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
结算 · 30 的子树和 80：节点 30 的左右子树和都齐了，结算：子树和 = 30 + 10 + 40 = 80。把 80 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
下钻 · 到叶子 -10：递归走到节点 -10（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
结算 · -10 的子树和 -10：节点 -10 的左右子树和都齐了，结算：子树和 = (-10)。把 -10 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
结算 · 20 的子树和 90：节点 20 的左右子树和都齐了，结算：子树和 = 20 + 80 + (-10) = 90。把 90 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
下钻 · 进入 80：递归进入节点 80（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
下钻 · 到叶子 40：递归走到节点 40（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
结算 · 40 的子树和 40：节点 40 的左右子树和都齐了，结算：子树和 = 40。把 40 记进哈希表，这个和之前出现过，计数涨到 2。节点变绿表示已经处理完。
下钻 · 到叶子 10：递归走到节点 10（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
结算 · 10 的子树和 10：节点 10 的左右子树和都齐了，结算：子树和 = 10。把 10 记进哈希表，这个和之前出现过，计数涨到 2。节点变绿表示已经处理完。
结算 · 80 的子树和 130：节点 80 的左右子树和都齐了，结算：子树和 = 80 + 40 + 10 = 130。把 130 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
结算 · 50 的子树和 270：节点 50 的左右子树和都齐了，结算：子树和 = 50 + 90 + 130 = 270。把 270 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
统计完成 · 扫计数表找最多：九个节点全部结算完，计数表也满了。现在扫一遍这张表，找出现次数最大的那个。可以看到 10 和 40 都出现了 2 次，其余的和都只出现 1 次，所以最大次数是 2。
得到答案 · 并列最多的全都要：次数等于 2 的和有两个：10 和 40，它俩并列最多。题目要求把出现次数最多的和全部返回，所以答案是 [10, 40]。这也提醒我们：最多的可能不止一个，别只返回一个就交卷。
边界要想清：单节点直接返回；全部各出现一次时，所有和都是答案。
面试可追问爆栈与一次成型，思路都围绕「后序结算 + 边算边记」。
参考代码
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 findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]: cnt = Counter() def dfs(node): if not node: return 0 s = node.val + dfs(node.left) + dfs(node.right) cnt[s] += 1 return s dfs(root) if not cnt: return [] best = max(cnt.values()) return sorted([s for s, c in cnt.items() if c == best])复杂度
- 时间：O(n)，每个节点只在后序里被访问、结算一次，哈希表的记一笔和最后扫表都是均摊 O(1)
- 空间：O(n)，哈希表最多存 n 个不同的子树和；递归栈深为树高 h，最坏（链状树）也是 O(n)
易错点
面试追问把动画讲成自己的话
追问如果树非常深，递归会不会爆栈？怎么办？
追问怎么一次遍历就同时拿到最大次数和答案？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
在每个树行中找最大值
LeetCode 515 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题