LeetCode 题解工作台
二叉树的堂兄弟节点 II
给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。 如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。 请你返回修改值之后，树的根 root 。 注意 ，一个节点的深度指的是从树根节点到这个节点经过的边数。 示例 1： 输入： root…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们创建一个列表 用于记录二叉树每一层的节点值之和，其中 表示第 层的节点值之和（规定根节点所在的层为第 层）。 接下来，我们先跑一遍 DFS，计算出数组 的值。然后再跑一遍 DFS，更新每个节点的子节点的值，子节点的值等于子节点所在层的节点值之和减去子节点及其兄弟节点的值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。
如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。
请你返回修改值之后，树的根 root 。
注意，一个节点的深度指的是从树根节点到这个节点经过的边数。
示例 1：
输入：root = [5,4,9,1,10,null,7] 输出：[0,0,0,7,7,null,11] 解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。 - 值为 5 的节点没有堂兄弟，所以值修改为 0 。 - 值为 4 的节点没有堂兄弟，所以值修改为 0 。 - 值为 9 的节点没有堂兄弟，所以值修改为 0 。 - 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。 - 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。 - 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。
示例 2：
输入：root = [3,1,2] 输出：[0,0,0] 解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。 - 值为 3 的节点没有堂兄弟，所以值修改为 0 。 - 值为 1 的节点没有堂兄弟，所以值修改为 0 。 - 值为 2 的节点没有堂兄弟，所以值修改为 0 。
提示：
- 树中节点数目的范围是
[1, 105]。 1 <= Node.val <= 104
解题思路
方法一：两次 DFS
我们创建一个列表 用于记录二叉树每一层的节点值之和，其中 表示第 层的节点值之和（规定根节点所在的层为第 层）。
接下来，我们先跑一遍 DFS，计算出数组 的值。然后再跑一遍 DFS，更新每个节点的子节点的值，子节点的值等于子节点所在层的节点值之和减去子节点及其兄弟节点的值。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# 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 = right
class 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) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for depth and parent tracking in your solution.
- question_mark
Hash Table usage to store per-level sums is expected.
- question_mark
Consider two-pass DFS instead of recomputing cousin sums repeatedly.
常见陷阱
外企场景- error
Failing to subtract sibling sums when calculating cousins, leading to incorrect node values.
- error
Ignoring nodes with no cousins and not setting their value to 0.
- error
Using a single DFS without tracking parents may mix up cousin calculations.
进阶变体
外企场景- arrow_right_alt
Compute product instead of sum of cousins per node.
- arrow_right_alt
Return a list of cousin sums instead of modifying the tree in place.
- arrow_right_alt
Limit cousin sums to nodes with exactly two cousins at each level.