NeetCode #429LC-2641MediumTrees
← Back to All Problems#429 · #2641 · Cousins in Binary Tree II(二叉树的堂兄弟节点 II)
📌 Problem Statement & Constraints
Given the root of a binary tree, replace each node's value with the sum of all values on the same level that are not its cousins' -- precisely, with
level_sum - sibling_sum, where sibling_sum is the sum of the node and its sibling. The root becomes 0. Constraints: the number of nodes is in [1, 10^5], 1 <= Node.val <= 10^4.💡 Core Algorithmic Approaches
- Process level by level. For each level, compute the total sum of its values.
- For each node on that level, its two children's new value is
level_sum - (this node's children sum)-- because a child's cousins are all nodes on the next level except itself and its sibling. - The root is set to 0 because it has no cousins.
- Doing this level by level guarantees the old values are used for
level_sumbefore any overwriting.
💻 Benchmark Python3 Implementation
class Solution:
def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
from collections import deque
root.val = 0 # the root has no cousins
q = deque([root])
while q:
level_sum = sum(node.val for node in q) # old values, before overwriting
nxt = deque()
for node in q:
sibling_sum = 0
if node.left:
sibling_sum += node.left.val
if node.right:
sibling_sum += node.right.val
# a child's new value excludes itself and its sibling
if node.left:
node.left.val = level_sum - sibling_sum
nxt.append(node.left)
if node.right:
node.right.val = level_sum - sibling_sum
nxt.append(node.right)
q = nxt
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(w) for the widest level.
⚠️ Interview Pitfalls & Follow-ups
- Computing
level_sumafter overwriting the children: the sum must come from the old values, so it is computed before the loop that writes. - Subtracting only the sibling's value: the node itself is also excluded, hence
level_sum - sibling_sumwheresibling_sumincludes both children of the parent. - Leaving the root unchanged: it must become 0.
- Handling a node with one child:
sibling_sumis just that child's value, and the child's new value islevel_sum - sibling_sum-- correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Trees Problems
中文速览与面试要点
二叉树的堂兄弟节点 II
给你一棵二叉树的根 root,请你将每个节点的值替换成该节点的所有 堂兄弟节点 值的和。如果两个节点在树中有相同的深度且它们的父节点不同,那么它们互为堂兄弟。请你返回修改值之后,树的根 root。注意,一个节点的深度指的是从树根节点到这个节点经过的边数。约束:树中的节点数在范围 [1, 10^5] 内;1 ≤ Node.val ≤ 10^4。
核心要点
- BFS 逐层 + 兄弟和扣减(标准解) :对每一层,先求该层的总和 total ;然后对每个节点 n,计算它两个孩子的和 sibling_sum ,把孩子的新值设为 total − sibling_sum 。
- 为什么这样正确 :堂兄弟 = 同层但不同父。对节点 n 的孩子 x 而言,同层的其他节点就是「本层所有节点中排除 n 的两个孩子」,因此总和为 total − sibling_sum 。
- 根节点的处理 :根没有堂兄弟,应置为 0。
- 必须用「本层原始值」求 total :若边求边改,后续节点的 total 会被污染。本解在修改前先算好 total,且修改的是 下一层 的节点值,因此安全。
常见陷阱
- 边遍历边修改导致 total 被污染 :必须先算好本层 total,再统一修改下一层的值。
- 根节点的值未置 0 :根没有堂兄弟,应置 0。
- 「兄弟和」只算一个孩子 :必须把当前节点的 两个 孩子的值都算进去。
- 忘记把子节点入队 :会导致只处理根节点一层。
参考实现
from collections import deque
class Solution:
def replaceValueInTree(self, root: 'TreeNode') -> 'TreeNode':
root.val = 0 # 根没有堂兄弟
q = deque([root])
while q:
level = [q.popleft() for _ in range(len(q))]
total = sum(n.val for n in level) # 本层总和(此时值尚未被改)
for n in level:
# 两个孩子之和(即「兄弟和」)
sibling = (n.left.val if n.left else 0) + (n.right.val if n.right else 0)
new_val = total - sibling # 堂兄弟之和
if n.left:
n.left.val = new_val
if n.right:
n.right.val = new_val
for n in level:
if n.left:
q.append(n.left)
if n.right:
q.append(n.right)
return root