| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13358 | DS_2021_Quiz3_BinaryTree |
|
Description
Given a binary tree, we define a magic jump M of level L in the binary tree B the value of the maximum possible node number between two existing nodes in level L. In this quiz, you are asked to print the maximum jump among all the levels in the tree. Please note that the calculation of M includes these two existing nodes. If there is only 0 or 1 node in this, M = 0.
We present several examples below. The solid black lines represent real edges and nodes, and the dotted lines/nodes represent edges and nodes that do not exist. They are depicted just for the ease of illustration.
Example 1.
In example 1, the magic jump in each level is:
level 1 = 0 (just root node)
level 2 = 2 (between nodes 2 and 3)
level 3 = 0 (just node 4)
Therefore, the answer is max{0,2,0}=2.
Example 2.
In example 2, the magic jump in each level is:
level 1 = 0 (just root node)
level 2 = 2 (between node 2 and 3)
level 3 = 4 (there exist 2 node space between nodes 4 and 5, and thus 2+2 = 4)
level 4 = 8 (there exist 6 nodes space between nodes 6 and 10, and thus 6+2=8;
0 nodes space between node 6 and 7, and thus 0+2=2;
The magic jump in level 4 is max{2,8} = 8)
The answer is max{0,2,4,8}=8.
Example 3.
In example 3, the magic jump in each level is:
level 1 = 0 (just root node)
level 2 = 2 (between nodes 2 and 3)
level 3 = 4 (there exists 1 node space between nodes 4 and 5, and thus 1+2 = 3;
2 node space between nodes 4 and 7, and thus 2+2 = 4;
The magic jump in level 3 is max{3,4} = 4)
Therefore, the answer is max{0,2,4}=4.
Given several s-expression of binary trees, please find the maximum magic jump in this binary tree and print it with a new line.
Input
The input is composed of several s-expression of binary trees.
The length of each s-expression is at most 10,000,000.
The number of nodes in each tree is at most 536,870,912.
Each nodes’ weight is between 0 and 10. ► Note that the numbers in the s-expressions are the “node weights”, which have no meaning in this quiz. We keep the node weights to allow you directly using the s-expression parser in your homework.
YES, we encourage you to copy-paste your s-expression parser from your OWN homework.
However, please make sure YOU ARE NOT COPY-PASTING OTHER’s s-expression parser!
Output
maximum magic jumps of all binary trees with new line after each output