Cousins in Binary Tree II

Leetcode Problem:

• Cousins in Binary Tree II

Summary

• Replace the value of each node in the binary tree with the sum of all its cousins' values.

Approach

• The approach is to use a level-order traversal (BFS) to calculate the sum of all cousins for each node
• Then, update the value of each node with the sum of its cousins.

Complexity

• O(n), where n is the number of nodes in the tree, since each node is visited once.

Explanation

• The solution uses a queue to perform a level-order traversal of the tree
• It calculates the sum of all cousins for each node by pushing the node and its children into the queue, then popping the node and adding its children to the queue
• The sum of all cousins is then calculated and used to update the value of the node.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
            root->val = 0;
    queue q;  q.push(root);
    while(!q.empty()){
        int n = q.size(), sum = 0;
        vector buf;
        while(n--){
            TreeNode* node = q.front(); q.pop();
            buf.push_back(node);
            if(node->left) { q.push(node->left); sum += node->left->val; }
            if(node->right){ q.push(node->right); sum += node->right->val; }
        }
        for(auto node: buf){
            int  t = sum;
            if(node->left)  t -= node->left->val;
            if(node->right) t -= node->right->val;
            if(node->left)  node->left->val = t;
            if(node->right) node->right->val = t;
        }
    }
    return root;
    }
};