Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1385
Question Name: Construct Binary Tree
Question Description: With the result of pre-order and in-order traversal of a tree, construct the binary tree, and return its post-order traversal result..
Input: may contain multiple test cases. For each test case, the first line contains one integer n (1<=n<=1000), being the number of nodes in the binary tree. The second line is n integers (in the range of [1, 1000]), being the pre-order traversal result. The third line is the in-order traversal result.
Output: the post-order traversal result.
1 2 3 4 5 6 7 8 9 10 | Input: 8 1 2 4 7 3 5 6 8 4 7 2 1 5 3 8 6 8 1 2 4 7 3 5 6 8 4 1 2 7 5 3 8 6 Output: 7 4 2 5 8 6 3 1 No |
This question is completely the same as Construct Binary Tree from Preorder and Inorder Traversal by LeetCode.
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 | /** * Filename : ConstructBinaryTree.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-07-31 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.Stack; import java.util.Arrays; /** * Definition for binary tree and its operation. */ class BinaryTreeNode { public Object val; public BinaryTreeNode left; public BinaryTreeNode right; /** * The constructor of binary tree node. * @param x: an object to be the value of this ListNode. */ public BinaryTreeNode(Object x) { val = x; left = right = null; } } /** * Test class for rebuilding the binary tree. * @author Sheng Yu (codesays.com) */ public class ConstructBinaryTree { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int size = 0; ConstructBinaryTree treeBuilder = new ConstructBinaryTree(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Start a new test case. size = (int) st.nval; // Get the result of pre-order traversal. Integer[] preOrder = new Integer[size]; for (int i = 0; i < size; ++i) { st.nextToken(); preOrder[i] = (int) st.nval; } // Get the result of in-order traversal. Integer[] inOrder = new Integer[size]; for (int i = 0; i < size; ++i) { st.nextToken(); inOrder[i] = (int) st.nval; } // Rebuild the tree from the pre-order and in-order traversal result. BinaryTreeNode root = treeBuilder.rebuildTree(Arrays.asList(preOrder), Arrays.asList(inOrder)); if (root == null) { System.out.println("No"); } else { // Do a post order traversal. And show the result Object[] postOrder = treeBuilder.postOrder(root); for (int i = 0; i < size; ++i) { System.out.print(postOrder[i]); System.out.print(" "); } System.out.println(); } } } /** * Rebuild the binary tree from the pre-order and in-order traversal result. * @param preOrder : the pre order traversal result of the binary tree. * @param inOrder : the in order traversal result of the binary tree. * @return BinaryTreeNode : the head node of the rebuilt tree. * null if fails. */ public BinaryTreeNode rebuildTree(List<Integer> preOrder, List<Integer> inOrder) { // The size of pre-order and in-order traversal results should be the same. if (preOrder.size() != inOrder.size()) return null; // Reach the leaf. if (preOrder.size() == 1) { if (preOrder.get(0) == inOrder.get(0)) return new BinaryTreeNode(preOrder.get(0)); else return null; } // Create the root node of current (sub)tree. BinaryTreeNode root = new BinaryTreeNode(preOrder.get(0)); int splitPoint = inOrder.indexOf(preOrder.get(0)); if (splitPoint == -1) return null; // Create the left son recursively, if exist. BinaryTreeNode left = null; if (splitPoint != 0) { left = rebuildTree(preOrder.subList(1, 1+splitPoint), inOrder.subList(0, splitPoint)); if (left == null) return null; } root.left = left; // Create the right son recursively, if exist. BinaryTreeNode right = null; if (splitPoint != inOrder.size()-1) { right = rebuildTree(preOrder.subList(1+splitPoint, preOrder.size()), inOrder.subList(1+splitPoint, inOrder.size())); if (right == null) return null; } root.right = right; return root; } /** * Get the result of post-order traversal o given binary tree. * @param root : the root of a binary tree. * @return Object[] : the result of post-order traversal on the rebuilt tree. */ public Object[] postOrder(BinaryTreeNode root) { Stack<BinaryTreeNode> prepare = new Stack<BinaryTreeNode>(); Stack<BinaryTreeNode> toVisit = new Stack<BinaryTreeNode>(); prepare.add(root); BinaryTreeNode current = null; while (!prepare.empty()) { current = prepare.pop(); if (current.left != null) prepare.add(current.left); if (current.right != null) prepare.add(current.right); toVisit.add(current); } ArrayList<Object> result = new ArrayList<Object>(); while (!toVisit.empty()) { current = toVisit.pop(); result.add(current.val); } return result.toArray(); } } |