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.