Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: make the last element of the postorder array as the root, then find the root value in the inorder array. Partition the inorder array into left and right parts. Call the buildTree function recursively. Very similar to the "Construct Binary Tree from Preorder and Inorder Traversal" problem.

Java语言: BuildTreeInorderPostorder

01 public TreeNode buildTree(int[] inorder, int[] postorder) {
02     int length=inorder.length;
03     return buildTree(inorder, 0, length-1, postorder, 0, length-1);
04 }
05 public TreeNode buildTree(int[] inorder, int start1, int end1, int []postorder, int start2, int end2)
06 {
07     if(start1>end1)
08         return null;
09     int value = postorder[end2];
10     int index = search(inorder, start1, end1, value);
11     TreeNode root = new TreeNode(value);
12     TreeNode left=buildTree(inorder, start1, index-1, postorder, start2, start2+index-start1-1);
13     TreeNode right=buildTree(inorder,index+1,end1,postorder, end2-(end1-index),end2-1);
14     root.left=left;
15     root.right=right;
16     return root;
17 }
18 
19 public int search(int[] array, int start, int end, int target)
20 {
21     for(int i=start;i<=end; i++)
22     {
23         if(array[i]==target)
24             return i;
25     }
26     return -1;
27 }