Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins’ values.Two nodes of a binary tree are cousins if they have the same depth with different parents.Return the root of the modified tree.Note that the depth of a node is the number of edges in the path from the root node to it.
Explanation: Node with value 5 does not have any cousins so its sum is 0. Node with value 4 does not have any cousins so its sum is 0. Node with value 9 does not have any cousins so its sum is 0. Node with value 1 has a cousin with value 7 so its sum is 7. Node with value 10 has a cousin with value 7 so its sum is 7. Node with value 7 has cousins with values 1 and 10 so its sum is 11.
Input: root = [3,1,2]Output: [0,0,0]
Explanation: Node with value 3 does not have any cousins so its sum is 0. Node with value 1 does not have any cousins so its sum is 0. Node with value 2 does not have any cousins so its sum is 0.
from collections import dequefrom leetcode_py import TreeNodeclass Solution: # Time: O(n) # Space: O(n) def replace_value_in_tree(self, root: TreeNode[int] | None) -> TreeNode[int] | None: if root is None: return None queue: deque[TreeNode[int]] = deque([root]) root.val = 0 while queue: next_sum = 0 for node in queue: for child in (node.left, node.right): if child is not None: next_sum += child.val for _ in range(len(queue)): node = queue.popleft() left, right = node.left, node.right child_sum = 0 if left is not None: child_sum += left.val if right is not None: child_sum += right.val for child in (left, right): if child is not None: child.val = next_sum - child_sum queue.append(child) return root
