LeetCode 题解工作台
修改后子树的大小
给你一棵 n 个节点且根节点为编号 0 的树，节点编号为 0 到 n - 1 。这棵树用一个长度为 n 的数组 parent 表示，其中 parent[i] 是第 i 个节点的父亲节点的编号。由于节点 0 是根， parent[0] == -1 。 给你一个长度为 n 的字符串 s ，其中 s[i]…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一棵 n 个节点且根节点为编号 0 的树，节点编号为 0 到 n - 1 。这棵树用一个长度为 n 的数组 parent 表示，其中 parent[i] 是第 i 个节点的父亲节点的编号。由于节点 0 是根，parent[0] == -1 。
给你一个长度为 n 的字符串 s ，其中 s[i] 是节点 i 对应的字符。
对于节点编号从 1 到 n - 1 的每个节点 x ，我们 同时 执行以下操作 一次 ：
- 找到距离节点
x最近 的祖先节点y，且s[x] == s[y]。 - 如果节点
y不存在，那么不做任何修改。 - 否则，将节点
x与它父亲节点之间的边 删除 ，在x与y之间连接一条边，使y变为x新的父节点。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是 最终 树中，节点 i 为根的 子树 的 大小 。
示例 1：
输入：parent = [-1,0,0,1,1,1], s = "abaabc"
输出：[6,3,1,1,1,1]
解释：
节点 3 的父节点从节点 1 变为节点 0 。
示例 2：
输入：parent = [-1,0,4,0,1], s = "abbba"
输出：[5,2,1,1,1]
解释：
以下变化会同时发生：
- 节点 4 的父节点从节点 1 变为节点 0 。
- 节点 2 的父节点从节点 4 变为节点 1 。
提示：
n == parent.length == s.length1 <= n <= 105- 对于所有的
i >= 1，都有0 <= parent[i] <= n - 1。 parent[0] == -1parent表示一棵合法的树。s只包含小写英文字母。
解题思路
方法一
class Solution:
def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]:
def dfs(i: int, fa: int):
ans[i] = 1
d[s[i]].append(i)
for j in g[i]:
dfs(j, i)
k = fa
if len(d[s[i]]) > 1:
k = d[s[i]][-2]
if k != -1:
ans[k] += ans[i]
d[s[i]].pop()
n = len(s)
g = [[] for _ in range(n)]
for i in range(1, n):
g[parent[i]].append(i)
d = defaultdict(list)
ans = [0] * n
dfs(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each node is visited once during DFS and hash updates. Space complexity is O(n) for the adjacency list and hash maps storing character counts for each subtree. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify adjacency list conversion for parent array.
- question_mark
Look for correct DFS traversal and aggregation logic per subtree.
- question_mark
Check handling of simultaneous parent changes without intermediate errors.
常见陷阱
外企场景- error
Updating subtree sizes incrementally can lead to incorrect counts due to simultaneous changes.
- error
Using only the parent array without adjacency mapping may cause inefficient traversal.
- error
Ignoring character aggregation when computing subtree sizes leads to wrong results.
进阶变体
外企场景- arrow_right_alt
Compute subtree sums based on numeric node values instead of character frequencies.
- arrow_right_alt
Handle dynamic insertion or deletion of nodes and recalculate subtree sizes.
- arrow_right_alt
Find the largest subtree satisfying a certain character or numeric condition after updates.