⚡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

中文速览与面试要点

二叉树的堂兄弟节点 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