In this problem you change the serialization approach used for a binary tree storing integer values. The tree will have been serialized using a level-order traversal, and you must output it given must translate it to a serialization using a pre-order traversal.
Note that the serialized tree, given as input, is generated as though there were nodes at each null child pointer. These nodes are listed in the input as having a value -.
Constraint on your solution: Your solution must deserialize the tree by making use of a TreeNode class which stores a data field, an LC field, and an RC field.
Notes:
Some of the test cases are very large, and may require you to speed up input and output handling. Note that you only need to try this if you are getting a time limit exceeded error when submitting your solution.
In C++, for example, you can include the following line as the first line in your main function to speed up the reading from input:
std::ios_base::sync_with_stdio (false);
And in Java, you can use a BufferedReader to greatly speed up reading from input, e.g.:
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// Read next line of input which contains an integer:
int T = Integer.valueOf(reader.readLine());
Furthermore, in Java, you can speed up output by collecting all of your output in a StringBuffer, and then making just one call to System.out.print, e.g.:
// This would be slow
for (int i = 0; i < 1000000; i++) {
System.out.println(i);
}
// This would be much faster
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 1000000; i++) {
sb.append(i);
sb.append("n");
}
System.out.println(sb.toString());
Input Format
The input consists of list of node values (including - for the null nodes listed above), one per line, as they would be visited in a level-order traversal.
Constraints
Each node value will be an integer with a value between -109 and 109. The total number of nodes in the tree (including the null nodes) will be less than 5 * 105.
Output Format
You should output the nodes as they would be printed in a pre-order traversal of the tree, including the - symbol for null nodes as in the input.
Sample Input
1
5
-8
-
2
3
4
6
-
-
-
-
-7
-
-
-
-
Sample Output
1
5
-
2
6
-
-
-
-8
3
-
-
4
-
-7
-
-
Explanation
The tree in the input would be deserialized as: see image.
In this project, you will be given a serialized binary tree storing integer values. You must find the subtree in the tree whose values sum to the largest value. Note that the serialized tree, given as input, is generated as though there were nodes at each null child pointer. These nodes are listed in the input as having a value -.
Constraints on your solution:
Your solution must deserialize the tree by making use of a TreeNode class which stores a data field, an LC field, and an RC field.
Other than possibly the root, you may not use any global/instance variables in solving this problem.
You must find the solution by writing a recursive method/function. The only parameter that this function may take is a reference/pointer to a node.
Notes:
Some of the test cases are very large, and may require you to speed up input handling. Note that you only need to try this if you are getting a time limit exceeded error when submitting your solution.
In C++, for example, you can include the following line as the first line in your main function to speed up the reading from input:
std::ios_base::sync_with_stdio (false);
And in Java, you can use a BufferedReader to greatly speed up reading from input, e.g.:
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); // Read next line of input which contains an integer: int T = Integer.valueOf(reader.readLine()); Input Format
The input consists of list of node values (including - for the null nodes listed above), one per line, as they would be visited in a level-order traversal.
Constraints
Each node value will be an integer with a value between -109 and 109. The total number of nodes in the tree (including the null nodes) will be less than 5 * 105.
Output Format
You should output the largest sum of all of the subtrees in the tree.
Notes:
The subtree rooted at a node r consists of all the nodes which are descendants of r.
All trees contain at least one empty subtree. The sum of values in an empty subtree is equal to 0.
Sample Input
1
5
-8
-
2
3
4
6
-
-
-
-
-7
-
-
-
-
Sample Output
13
Explanation
The tree in the input would be deserialized as: see image.
This tree consists of the following subtrees:
Root Value Subtree Sum
1 6
5 13
-8 -8
2 8
6 6
3 3
4 -3
-7 -7
empty 0
You should output 13, which is the maximum subtree sum.