Solution to Mirror Of Binary Tree from Jobdu

10 Aug

Question (in Chinese):

Question Name: Mirror Of Binary Tree

Question Description: Give a binary tree, find its mirror copy and print it out in pre-order.

Input: the input might contain multiple test cases. Inside each test case, the first line includes one interger N (0 <= N <= 1000), saying the size of the binary tree. The second line includes N integers, as the value of each node in the tree (the first node is the root node). Then the following N lines have three four formations. The i(th) line is
1. Character “z” means the (i)th node has no child; OR
2. Character “l” and one integer LS,  means the  (i)th node has (LS)th node as its left son; OR
3. Character “r” and one integer RS,  means the  (i)th node has (RS)th node as its right son; OR
4. Character “d” and two integers LS and RS, means the  (i)th node has (LS)th node as its left son, and (RS)th node as its right son.
PS: both the line NO. and the nodes are 1-based index.

Output: “NULL” if the tree is empty. Otherwise, print out the value of the mirrored tree in pre-order.

The official solution is done in a recursive way. And here is my iterative solution.

Leave a Reply

Your email address will not be published. Required fields are marked *