1 /**
 2      * Given inorder and postorder traversal of a tree, construct the binary tree.
 3      * @param inorder
 4      * @param postorder
 5      * @return
 6      */
 7     public TreeNode buildTree(int[] inorder,int[] postorder){
 8         if(inorder == null || postorder ==null 
 9                 || inorder.length == 0 || postorder.length == 0)
10             return null;
11         if(inorder.length!=postorder.length)
12             return null;
13         if(inorder.length == 1)
14         {
15             if(inorder[0] != postorder[0])
16                 return null;
17             else
18                 return new TreeNode(inorder[0]);
19         }
20         // make sure how many nodes in the left
21         int i=0;
22         while(inorder[i++] != postorder[postorder.length-1]);
23         int[] leftInorder = new int[i-1];
24         int[] leftPostorder = new int[i-1];
25         int j = 0;
26         while(j<i-1){
27             leftInorder[j] = inorder[j];
28             leftPostorder[j] = postorder[j];
29             j++;
30         }
31         TreeNode left = buildTree(leftInorder, leftPostorder);
32         TreeNode root = new TreeNode(postorder[postorder.length-1]);
33         root.left = left;
34         // find the right subtree nodes
35         int[] rightInorder = new int[inorder.length - (i-1) -1];
36         int[] rightPostorder = new int[postorder.length - (i-1) -1];
37         
38         j = i;
39         while(j<inorder.length){
40             rightInorder[j-i] = inorder[j];
41             rightPostorder[j-i] = postorder[j-1];
42             j++;
43         }
44         root.right = buildTree(rightInorder,rightPostorder);
45         
46         return root;
47     }
48     /**
49      * Given preorder and inorder traversal of a tree, 
50      * construct the binary tree.
51      * @param preorder
52      * @param inorder
53      * @return
54      */
55     public TreeNode buildTree2(int[] preorder, int[] inorder){
56         if(preorder == null || inorder == null ||
57                 preorder.length == 0 || inorder.length == 0)
58             return null;
59         if(preorder.length != inorder.length)
60             return null;
61         int len = 0;
62         while(inorder[len++]!=preorder[0]);
63         //determine the left subtree
64         int[] leftInorder = new int[len-1];
65         int[] leftPreorder = new int[len-1];
66         
67         int j =0;
68         while(j<len-1)
69         {
70             leftInorder[j] = inorder[j];
71             leftPreorder[j] = preorder[j+1];
72             j++;
73         }
74         
75         TreeNode left = buildTree( leftPreorder,leftInorder);
76         TreeNode root = new TreeNode(preorder[0]);
77         root.left =left;
78         //determine the right subtree
79         int[] rightInorder = new int[inorder.length - (len-1) -1];
80         int[] rightPreorder = new int[preorder.length - (len-1) -1];
81         j = len;
82         while(j<inorder.length){
83             rightInorder[j-len] = inorder[j];
84             rightPreorder[j-len] = preorder[j];
85             j++;
86         }
87         root.right = buildTree(rightPreorder,rightInorder);
88         return root;
89     }