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.
Example 1:
Input: root = [5,4,9,1,10,null,7] Output: [0,0,0,7,7,null,11] Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node. - 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.
Example 2:
Input: root = [3,1,2] Output: [0,0,0] Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node. - 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.
Constraints:
[1, 105].1 <= Node.val <= 104This approach utilizes a breadth-first search (BFS) to traverse each level of the binary tree and calculate the sum of cousin values for each node. We maintain a queue to process each level separately and keep track of parent nodes to ensure calculations of cousins are accurate. This allows us to update the tree with the required values.
This solution uses a typical BFS approach to traverse the tree and calculate the value of cousins for each node. We can modify this to calculate the cousin sum and then update each node in the binary tree. For simplicity, the function `modifyTree` is a placeholder where we will implement the logic.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes in the tree since each node is processed a constant number of times.
Space Complexity: O(W), where W is the maximum width of the tree (number of nodes at the widest level) due to the queue.
This approach leverages a depth-first search (DFS) strategy in combination with a hash map to keep track of nodes and their parents at each depth level. This allows easy computation of cousin sums to modify tree node values.
This solution in C uses depth-first traversal to explore each node in a binary tree and a hash map-like strategy (indicated in comments) to track the nodes and calculate the sum of cousins for tree nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N)
Space Complexity: O(H), where H is the height of the tree.
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search with Level Tracking | Time Complexity: O(N), where N is the number of nodes in the tree since each node is processed a constant number of times. |
| Approach 2: Depth-First Search with HashMap for Cousin Tracking | Time Complexity: O(N) |
Cousins in a binary tree | Leetcode #993 • Techdose • 37,620 views views
Watch 9 more video solutions →Practice Cousins in Binary Tree II with our built-in code editor and test cases.
Practice on FleetCode