public TreeNode replaceValueInTree(TreeNode root) {
//root always be 0
root.val = 0;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
//calculate the total sum of each level
// final values of nodes with parent A will then be > sum - (sum of all nodes that have parent A)
int sum = 0;
// this will keep track of each parent with which we are able to
// update this child's cousin's value
List<TreeNode> list = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode cur = queue.poll();
if(cur.left != null){
sum += cur.left.val;
}
if(cur.right != null){
sum += cur.right.val;
}
list.add(cur);
}
// for all the tracked parents in the order, update their child's value with sum of cousins
for(TreeNode parent : list){
int levelSum = sum;
if(parent.left != null){
levelSum -= parent.left.val;
queue.offer(parent.left);
}
if(parent.right != null){
levelSum -= parent.right.val;
queue.offer(parent.right);
}
//update the values
if(parent.left != null){
parent.left.val = levelSum;
}
if(parent.right != null){
parent.right.val = levelSum;
}
}
}
return root;
}
}