(TreeNode root)
| 1 | class Solution { |
| 2 | public TreeNode replaceValueInTree(TreeNode root) { |
| 3 | //bfs |
| 4 | Queue<TreeNode> queue = new LinkedList<>(); |
| 5 | queue.offer(root); |
| 6 | int prevSum = root.val; |
| 7 | while(!queue.isEmpty()){ |
| 8 | int size = queue.size(); |
| 9 | int curSum=0; |
| 10 | for(int i=0;i<size;i++){ |
| 11 | TreeNode node = queue.poll(); |
| 12 | node.val = prevSum-node.val; |
| 13 | int sibsum=0; |
| 14 | if(node.left!=null){ |
| 15 | sibsum+=node.left.val; |
| 16 | } |
| 17 | if(node.right!=null){ |
| 18 | sibsum+=node.right.val; |
| 19 | } |
| 20 | if(node.left!=null){ |
| 21 | curSum += node.left.val; |
| 22 | node.left.val = sibsum; |
| 23 | queue.offer(node.left); |
| 24 | } |
| 25 | if(node.right!=null){ |
| 26 | curSum += node.right.val; |
| 27 | node.right.val = sibsum; |
| 28 | queue.offer(node.right); |
| 29 | } |
| 30 | } |
| 31 | prevSum = curSum; |
| 32 | } |
| 33 | return root; |
| 34 | } |
| 35 | } |