Description

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

Construct_tree

Traverse

Height

WeightSum

MaximumPathSum

BinaryTower

DeleteLeaf

Foldable

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

Input

Input is composed by several sets of questions

A set of question will start by a s-expression string, then 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 10000000
2. The number of nodes in each tree is at most 1200000
3. Each nodes’ weight is between -100000 and 100000

Output

• Traverse : print preorder, inorder, postorder traversal of the binary tree
• Height : print the height 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**
• End : End of instructions of this question set.

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

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss