题目描述
思路解析动画文字版
记牢一句话: 每个节点向上交一份「子树里各字母出现几次」的统计, 父节点把孩子的统计合并再加上自己; 而 ans[i] 就是这份统计里节点 i 自己那个标签的次数。下面每一帧都在套这条规则。
总览 · 树与标签：先看清这棵树。紫色的节点 0 是根。它的两个孩子是 1 和 2; 节点 1 下面挂着 4 和 5, 节点 2 下面挂着 3 和 6。右边「标签表」记着每个节点的字母: 0 号 a, 1 号 b, 2 号 a, 3 号 e, 4 号 d, 5 号 c, 6 号 d。我们要给七个节点各算一个 ans, ans[i] 是它子树里和它同标签的节点数。
建图 · 无向边变邻接表：动手前先建邻接表。题目给的是无向边, 每条边的两个端点都要互相记成对方的邻居, 这样从任意点都能往四周走。然后把节点 0 当根, 从它出发往下走, 沿途遇到的节点就成了孩子。递归时带上父节点, 遇到父节点就跳过, 免得从孩子又走回父亲绕圈。方向定好, 这棵树就有了上下层级。
规则 · 每个节点返回什么：把规则在画面上钉死。每个节点要向上交一份统计: 它的子树里, 26 个小写字母分别出现了几次。父节点把所有孩子的统计逐字母相加, 再给自己的标签加 1, 就得到自己的统计。而某个节点的答案, 就是它这份统计里、自己那个标签出现的次数。带着这条规则, 开始后序搜索。
下行 · 进入根 0：后序深度优先搜索从根 0 开始。蓝色表示这个节点已经进入、正挂在搜索路径上, 但它的统计还没算出来, 因为得先把孩子那边都收完。节点 0 的标签是 a。先往它的第一个孩子 1 走下去。
下行 · 进入节点 1：走到节点 1, 它的标签是 b。现在还不能下结论, 因为它下面还挂着 4 和 5 两个孩子, 得先把孩子的统计收上来才能合并。继续往它的孩子里下探, 先去 4。
下行 · 进入叶子 4：走到节点 4, 标签是 d。它没有孩子, 是个叶子, 可以马上结算。叶子的子树就它自己一个节点, 统计也最简单。
结算 · 子树 4 统计 d×1：结算节点 4。它变绿, 代表这棵子树算完了。子树里只有它自己, 标签是 d, 所以统计是 d 出现 1 次。节点 4 自己的标签就是 d, 在统计里 d 出现 1 次, 所以 ans[4] 等于 1。节点 4 把这份 {d×1} 的统计交回给父亲 1。接着看 1 的另一个孩子 5。
下行 · 进入叶子 5：走到节点 5, 标签是 c, 它也是叶子, 同样可以直接结算。和刚才的 4 一样, 子树里只有它自己一个节点。
结算 · 子树 5 统计 c×1：结算节点 5。它变绿, 子树里只有自己, 标签是 c, 统计就是 c 出现 1 次。节点 5 自己的标签 c 在统计里出现 1 次, 所以 ans[5] 等于 1。现在节点 1 的两个孩子都算完了: 4 交回 {d×1}, 5 交回 {c×1}。回到节点 1, 该把它们合并了。
回溯 · 回到节点 1 合并：回到节点 1。把两个孩子的统计逐字母相加: 孩子 4 带回 d 出现 1 次, 孩子 5 带回 c 出现 1 次, 两个字母不重叠, 合并后是 c 一次、d 一次。还差最后一步, 把节点 1 自己的标签也加进去。
结算 · 子树 1 统计 b1 c1 d1：结算节点 1。它自己的标签是 b, 给统计里 b 加 1, 子树 1 的完整统计就是 b 一次、c 一次、d 一次。节点 1 变绿。它自己的标签 b 在这份统计里出现 1 次, 所以 ans[1] 等于 1。注意子树 1 里虽然有三个节点, 但标签和 b 相同的只有节点 1 自己。节点 1 把这份统计交还给根 0。回根 0, 去看另一个孩子 2。
下行 · 进入节点 2：从根 0 走到另一个孩子 2, 它的标签是 a。它下面还挂着 3 和 6, 按后序还是要先把孩子看完, 才能合并出自己的统计。先去 3。
下行 · 进入叶子 3：走到节点 3, 标签是 e, 叶子, 直接结算。子树里只有它自己一个节点。
结算 · 子树 3 统计 e×1：结算节点 3。它变绿, 子树只有自己, 标签 e, 统计是 e 出现 1 次。自己的标签 e 出现 1 次, 所以 ans[3] 等于 1。节点 3 把 {e×1} 交回父亲 2。再看 2 的另一个孩子 6。
下行 · 进入叶子 6：走到节点 6, 标签是 d, 也是叶子。和前面几个叶子一样, 子树里只有它自己。
结算 · 子树 6 统计 d×1：结算节点 6。它变绿, 标签 d, 统计是 d 出现 1 次, ans[6] 等于 1。现在节点 2 的两个孩子都算完了: 3 交回 {e×1}, 6 交回 {d×1}。回到节点 2, 把它们合并。
回溯 · 回到节点 2 合并：回到节点 2。把孩子的统计逐字母相加: 孩子 3 带回 e 一次, 孩子 6 带回 d 一次, 合并后是 d 一次、e 一次。下一步把节点 2 自己的标签 a 加进去。
结算 · 子树 2 统计 a1 d1 e1：结算节点 2。它自己标签是 a, 给统计里 a 加 1, 子树 2 的完整统计是 a 一次、d 一次、e 一次。节点 2 变绿。它自己的标签 a 在统计里出现 1 次, 所以 ans[2] 等于 1。节点 2 把这份统计交还给根 0。现在根 0 的两个孩子都收齐了。
回溯 · 回到根 0 合并两支：回到根 0。把两支孩子的统计逐字母相加。子树 1 带回 b 一次、c 一次、d 一次; 子树 2 带回 a 一次、d 一次、e 一次。两份相加: a 一次, b 一次, c 一次, d 在两边各一次合成 2 次, e 一次。最后还要把根自己的标签 a 加进去。
结算 · 根 0 统计 a2 b1 c1 d2 e1：结算根 0。它自己标签是 a, 给统计里 a 再加 1, a 变成 2 次。整棵树的统计是 a 两次、b 一次、c 一次、d 两次、e 一次。根 0 自己的标签是 a, 在统计里 a 出现 2 次, 所以 ans[0] 等于 2。这两个 a 来自节点 0 自己和节点 2。整棵树搜完, 答案出来了。
回放 · ans 数组：回放一遍。整个过程只做了一次后序遍历: 从根下探到每个叶子, 再自底向上把每层的统计合并回来, 七个节点的 ans 一次就全算出来了。结果是 ans 等于 2, 1, 1, 1, 1, 1, 1。除了根节点是 2, 其它六个都是 1, 因为它们各自的子树里没有第二个同标签的节点。
对比 · 统计全部, 只读自己：最后看一处最容易绕晕的地方。根 0 的统计里, 字母 a 出现 2 次, 字母 d 也出现 2 次(来自节点 4 和节点 6)。可 ans[0] 只等于 2, 是因为它只看根自己那个标签 a 的次数。d 出现几次和根没关系。这就是核心: 合并时统计全部 26 个字母, 但每个节点的答案只读出它自己那个标签的次数。
边界看三种: 单节点答案是 1; 一条链上标签全相同, 答案就是各自子树的大小; 一条链上标签全不同, 每个答案都是 1。
面试重点: 返回完整 26 维统计才能让父层正确合并; n 大时递归可能爆栈, 改迭代或拓扑序; 单独数每个子树是 O(n²), 复用孩子结果才是 O(n) 的树形 DP。
参考代码
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 = nextclass Solution: def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]: def dfs(i, fa): ans[i] -= cnt[labels[i]] cnt[labels[i]] += 1 for j in g[i]: if j != fa: dfs(j, i) ans[i] += cnt[labels[i]] g = defaultdict(list) for a, b in edges: g[a].append(b) g[b].append(a) cnt = Counter() ans = [0] * n dfs(0, -1) return ans复杂度
- 时间：O(n)，建邻接表把每条边记两遍是 O(n)(树有 n-1 条边); 后序 DFS 每个节点只访问一次, 参考代码在每个节点上对计数器做常数次加减, 是 O(1)。两步都是线性, 总体 O(n)
- 空间：O(n)，邻接表存 2(n-1) 个邻居是 O(n); 递归栈深度是树高, 最坏退化成长链时是 O(n); 共享计数器只有 26 个格子是 O(1)。按峰值取最大, 空间 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么每个节点要返回完整的 26 字母统计, 只返回自己标签的数量行不行?
追问n 可以到十万, 递归会不会爆栈, 怎么处理?
追问为什么不能像普通做法那样, 对每个节点单独遍历一次它的子树来数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
好叶子节点对的数量
LeetCode 1530 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题