⚡Flashcard Drill➔
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

  1. Process level by level. For each level, compute the total sum of its values.
  2. 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.
  3. The root is set to 0 because it has no cousins.
  4. Doing this level by level guarantees the old values are used for level_sum before 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_sum after 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_sum where sibling_sum includes both children of the parent.
  • Leaving the root unchanged: it must become 0.
  • Handling a node with one child: sibling_sum is just that child's value, and the child's new value is level_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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems