Convert a Binary Tree to its Sum Tree

Given a binary tree of integers, convert it to a sum tree where each node is replaced by the sum of the values of its left and right subtrees. Set leaf nodes to zero.

Input:

The first line contains an integer 'T', the number of test cases.
For each test case, a line with elements in level order, with nodes separated by spaces. Use -1 for null nodes.

Output:

For each test case, return the level order traversal of the converted sum tree, with nodes separated by spaces, using -1 for NULL nodes.

Example:

Input:

1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

27 13 11 7 0 0 0

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• -104 <= val <= 104 and val != -1

Note: The input ends when all nodes at the last level are null (-1).