题目描述
思路解析动画文字版
记牢这一句:堂兄弟和 = 本层总和 减去 同父那一组的和。下面先把三层的总和算出来,再自上而下一个父亲一个父亲地发放。
初始的树 · 目标把每个值换成堂兄弟之和：这是初始的树,层序是 5,4,9,1,10,空,7。根 5 在第 0 层,4 和 9 在第 1 层,1、10、7 在第 2 层。我们的目标,是把每个节点的值,换成它所有堂兄弟节点的值之和。先把「谁和谁是堂兄弟」看清楚。
什么是堂兄弟 · 同层但不同父：看第 2 层这三个节点。1 和 10 的父亲都是 4,它俩是亲兄弟,不算堂兄弟。7 的父亲是 9,和 1、10 的父亲不一样。所以 7 与 1、10 才互为堂兄弟。抓住这个区别:同一层还不够,必须父亲不同。
第一趟 · 第 0 层求和：第一趟自上而下,把每一层的总和都求出来。第 0 层只有根节点 5,这一层的总和就是 5。记到右边面板里。
第一趟 · 第 1 层求和：第 1 层有 4 和 9 两个节点,它们相加是 13,这就是第 1 层的总和。注意这一层里 4 和 9 是亲兄弟,同一个父亲根 5 底下。
第一趟 · 第 2 层求和：第 2 层有 1、10、7 三个节点,相加是 18。三层的总和都算好了,分别是 5、13、18。第一趟到此结束,接下来第二趟开始发放。
看清同父分组 · 4 名下: 1 和 10：发放前先把「同父的组」看清楚。节点 4 底下的 1 和 10 是一组亲兄弟。等下算这两个孩子的堂兄弟和时,要从第 2 层总和里减掉的,正是这一组 1 加 10。
看清同父分组 · 9 名下: 只有 7：节点 9 底下只有右孩子 7,左孩子是空的。所以 9 名下这一组就只有 7 自己。等下算 7 的堂兄弟和,要减掉的就是它自己这一格。
第二趟起步 · 根没有堂兄弟：第二趟自上而下发放。先看根 5。它在第 0 层,整层就它一个,没有任何同层的伙伴,自然也没有堂兄弟。所以它的堂兄弟和是 0。
根改写为 0：把根改写成 0。注意这一改不影响后面的计算,因为算孩子时用的是孩子那一层的原始值,和根现在是几没关系。接着往下一层发放。
发放到第 1 层 · 看根的两个孩子 4 和 9：看根的两个孩子 4 和 9。它俩同层,而且同一个父亲根,是一组亲兄弟。它们所在的第 1 层总和是 13。堂兄弟和,就要拿这个 13 去减掉它们这一组自己的和。
算堂兄弟和 · 13 减 13：4 和 9 这一组自己的和是 4 加 9 等于 13,恰好等于整层总和 13。相减得到 0,说明它们在这一层里没有别的父亲的伙伴。所以 4 和 9 的堂兄弟和都是 0。
改写第 1 层 · 4 → 0, 9 → 0：把 4 和 9 都改写成 0。第 1 层发放完毕。继续往下,进入第 2 层,分别由 4 和 9 这两个父亲来发放。
父亲(原 4)发放 · 孩子 1 和 10：轮到左边这个父亲,它原来的值是 4,现在已经是 0 了。它名下有 1 和 10 两个孩子,都在第 2 层。第 2 层总和是 18,接下来拿它减掉 1 和 10 这一组自己的和。
算堂兄弟和 · 18 减 11：1 和 10 这一组自己的和是 1 加 10 等于 11。第 2 层总和 18 减去 11,得到 7。这个 7 就是它俩在第 2 层里、别的父亲那几个孩子的和,也就是它们唯一的堂兄弟 7。所以 1 和 10 都改成 7。
改写 · 1 → 7, 10 → 7：把 1 和 10 都改写成 7,和我们一开始说的答案对上了。左边这个父亲名下的孩子处理完,只剩右边父亲名下那个 7 了。
父亲(原 9)发放 · 只有一个孩子 7：轮到右边这个父亲,它原来是 9,现在也是 0 了。它只有右孩子 7,左孩子是空的。算 7 的堂兄弟和时,要从第 2 层总和里减掉的,就是这个父亲名下的孩子之和,也就是 7 自己加上空的那半边算 0。
算堂兄弟和 · 18 减 7：这个父亲名下的孩子之和是 0 加 7 等于 7。第 2 层总和 18 减去 7,得到 11。这个 11 正好是 7 在第 2 层里的两个堂兄弟 1 和 10 之和。所以 7 改成 11。
改写 · 7 → 11：把 7 改写成 11。至此,除根之外每个节点都拿到了它的堂兄弟之和,整棵树发放完毕。下面回头验一遍。
完成 · 最终的树：最终这棵树的层序变成 0、0、0、7、7、空、11。和官方给的答案一模一样。回顾一下每一步都在做同一件事:本层总和,减去同父那一组的和。
复核 · 每个节点对得上吗：逐个检验。节点 1 在第 2 层,同层里父亲不同的只有 7,所以它的堂兄弟和是 7,对得上。10 同理,堂兄弟也只有 7,改成 7。7 的堂兄弟是 1 和 10,和为 11,也对得上。根和第 1 层没有堂兄弟,全归 0。全部吻合。
边界想清:单节点归 0、只有一层亲兄弟也全归 0、示例里 1 换 7 而 7 换 11。
面试重点:两趟求层和加发放、减的是同父一组、也能一趟 BFS 边算下层和边回填。
参考代码
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 = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs1(root: Optional[TreeNode], depth: int): if root is None: return if len(s) <= depth: s.append(0) s[depth] += root.val dfs1(root.left, depth + 1) dfs1(root.right, depth + 1) def dfs2(root: Optional[TreeNode], depth: int): sub = (root.left.val if root.left else 0) + ( root.right.val if root.right else 0 ) depth += 1 if root.left: root.left.val = s[depth] - sub dfs2(root.left, depth) if root.right: root.right.val = s[depth] - sub dfs2(root.right, depth) s = [] dfs1(root, 0) root.val = 0 dfs2(root, 0) return root复杂度
- 时间：O(n)，n 是节点数。两趟遍历,每趟都恰好访问每个节点一次,每次只做常数次加减,总量随节点数线性增长
- 空间：O(h)，按峰值算。存每层总和的数组长度等于树高 h;递归栈深也是 h。二者都是 O(h),最坏树退化成一条链时 h 等于 n,即 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么减的是同父孩子之和,而不是节点自己的值?
追问能不能只用一趟 BFS 完成?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题