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:
- The number of nodes in the tree is in the range
[1, 105]. 1 <= Node.val <= 104
Companies: Amazon
Related Topics:
Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Similar Questions:
// OJ: https://leetcode.com/problems/cousins-in-binary-tree-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
TreeNode* replaceValueInTree(TreeNode* root) {
root->val = 0;
queue<TreeNode*> q{{root}};
while (q.size()) {
int cnt = q.size(), sum = 0;
queue<TreeNode*> p;
while (cnt--) {
auto n = q.front();
p.push(n);
q.pop();
if (n->left) {
q.push(n->left);
sum += n->left->val;
}
if (n->right) {
q.push(n->right);
sum += n->right->val;
}
}
while (p.size()) {
auto n = p.front();
p.pop();
int val = sum - (n->left ? n->left->val : 0) - (n->right ? n->right->val : 0);
if (n->left) n->left->val = val;
if (n->right) n->right->val = val;
}
}
return root;
}
};