Description

In this homework, we need to construct a tree from the s-expression and implement the following functions.

Construct_tree

Traverse

WeightSum

MaximumPathSum

Invert

DeleteLeaf

Foldable

BinaryTower

KingdomUnitedPath

You can use String in this homework. However, other kinds of STL are forbidden.

Input

Input is composed of several sets of questions.

A set of questions start by an s-expression string, followed by several instructions that end with the instruction “End”.

First, you’ll see an s-expression string. Then, you’ll see several instructions. Finally, you’ll see an “End” instruction, and after that you’ll see EOF or next s-expression string

Note:

1. The length of each s-expression is at most 10,000,000
2. The number of nodes in each tree is at most 1,200,000
3. Each nodes’ weight is between -100,000 and 100,000

Output

• Traverse: print preorder, inorder, postorder traversal of the binary tree
• WeightSum: print the sum of all the node’s weight in the binary tree
• MaximumPathSum: print the maximum sum among all root to leaf paths of the binary tree
• BinaryTower: print the number of towers needed to defend the hole binary tree
• DeleteLeaf: delete all the leaves in the binary tree
• Foldable: Print “Yes” or “No” Depending on the binary tree foldable or not. **without double quotes**
• Invert: flip the binary tree horizontally
• KindomUnitedPath: print the length of the longest alliance kingdom path
• End: End of instructions of this question set.

***The output of every Instructions except DeleteLeaf and Invert should followed by a new line ***

Sample Input  Download

Sample Output  Download

Tags

Discuss