Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1521
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | Input: 7 8 6 10 5 7 9 11 d 2 3 d 4 5 d 6 7 z z z z Output: 8 10 11 9 6 7 5 Appendix: the corresponding tree for the input 8 / 6 10 / / 5 7 9 1 |
The official solution is done in a recursive way. And here is my iterative solution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/10/2014 * Last updated: 08/10/2014 * * Filename: MirrorOfBinaryTree.java * Compilation: javac MirrorOfBinaryTree.java * Execution: java MirrorOfBinaryTree * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Stack; /** * This class include a definition of binary tree, and the function to * get a mirror copy of a given tree. * @author Sheng Yu codesays.com */ public class MirrorOfBinaryTree { /** * The definition of binary tree. * @author Sheng Yu codesays.com * @param <T> the type of the value in the node. */ private static class BinaryTreeNode<T> { /** The value of current node. */ private T value = null; /** The left of current node. */ private BinaryTreeNode<T> left = null; /** The right son of current node. */ private BinaryTreeNode<T> right = null; /** @return the value of this node. */ public T getValue() { return value; } /** @param newValue the new value of this node. */ public void setValue(final T newValue) { value = newValue; } /** @return the left son of this node. */ public BinaryTreeNode<T> getLeft() { return left; } /** @param newLeft the new left son of this node. */ public void setLeft(final BinaryTreeNode<T> newLeft) { left = newLeft; } /** @return the right son of this node. */ public BinaryTreeNode<T> getRight() { return right; } /** @param newRight the new right son of this node. */ public void setRight(final BinaryTreeNode<T> newRight) { right = newRight; } } /** * Do a pre-order visit to the given tree. * @param root the root node of the binary tree. * @return a string representing the content in the tree. */ @SuppressWarnings("rawtypes") public final String preOrderVisit(final BinaryTreeNode root) { if (root == null) { // Empty tree. return "NULL"; } StringBuilder sb = new StringBuilder(); Stack<BinaryTreeNode> nodes = new Stack<BinaryTreeNode>(); nodes.push(root); BinaryTreeNode current = null; while (!nodes.empty()) { current = (BinaryTreeNode) nodes.pop(); sb.append(current.getValue().toString()); sb.append(" "); if (current.getRight() != null) { // Right sub-tree nodes.push(current.getRight()); } if (current.getLeft() != null) { // Left sub-tree nodes.push(current.getLeft()); } } sb.setLength(sb.length() - 1); // Skip the last space. return sb.toString(); } /** * Covert a tree to its mirror in place. * @param root the root node of the to-covert binary tree. */ @SuppressWarnings({ "rawtypes", "unchecked" }) public final void convert2Mirror(final BinaryTreeNode root) { if (root == null) { // Empty tree return; } // Do a pre-order traversal. Stack<BinaryTreeNode> nodes = new Stack<BinaryTreeNode>(); nodes.push(root); BinaryTreeNode<Object> left = null, right = null, current = null; while (!nodes.empty()) { current = (BinaryTreeNode<Object>) nodes.pop(); left = current.getLeft(); right = current.getRight(); // Swap the left son and right son. current.setLeft(right); current.setRight(left); if (right != null) { // Waiting to process the right subtree. nodes.push(right); } if (left != null) { // Waiting to process the left subtree. nodes.push(left); } } return; } /** * Test stub. * @param args the command line arguments. * @throws IOException when input gets error. */ @SuppressWarnings("unchecked") public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); BinaryTreeNode<Integer>[] tree = null; BinaryTreeNode<Integer> root = null; MirrorOfBinaryTree mirror = new MirrorOfBinaryTree(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the size of the two trees. tree = null; if ((int) st.nval > 0) { tree = (BinaryTreeNode<Integer>[]) new BinaryTreeNode[(int) st.nval]; } // Get the content of the two trees. if (tree != null) { // Get the value of each node. for (int i = 0; i < tree.length; ++i) { st.nextToken(); tree[i] = new BinaryTreeNode<Integer>(); tree[i].setValue((int) st.nval); } // Get the son information. for (int i = 0; i < tree.length; ++i) { st.nextToken(); if (st.sval.equals("d")) { // Has both left and right sons. st.nextToken(); tree[i].setLeft(tree[((int) st.nval) - 1]); st.nextToken(); tree[i].setRight(tree[((int) st.nval) - 1]); } else if (st.sval.equals("l")) { // Has only left son. st.nextToken(); tree[i].setLeft(tree[((int) st.nval) - 1]); } else if (st.sval.equals("r")) { // Has only right son. st.nextToken(); tree[i].setRight(tree[((int) st.nval) - 1]); } else if (st.sval.equals("z")) { // No son. } else { // Invalid input. throw new IllegalArgumentException("Invalid son info."); } } } // Find the root node. if (tree == null) { root = null; } else { root = tree[0]; } // Mirror the tree. mirror.convert2Mirror(root); System.out.println(mirror.preOrderVisit(root)); } } } |