106. Construct Binary Tree from Inorder and Postorder Traversal Leetcode Java

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:

Same technique as 105. Construct Binary Tree from Preorder and Inorder Traversal

Instead of finding the postion of the preorder's first element in Inorder array, we find the position of Postorder's last element in Inorder array, because, the root is the last element in Postorder array. 

The solution is also very similar to previous problem, so I am not going to give the detail here. 

Here I use a hashmap to store the index/positon of particular value for Inorder array. So when we can find the position of the root in Inorder array more efficient in O(1) time rather than search the array everytime in O(n) time. Extra O(n) space of hashmap is needed to improve the time performance. Both methods can pass the OJ.

 public TreeNode buildTree(int[] inorder, int[] postorder) {  
     if(inorder==null || postorder==null || inorder.length!=postorder.length) return null;  
     HashMap<Integer, Integer> index=new HashMap<Integer,Integer>();  
     for(int i=0;i<inorder.length;i++){  
       index.put(inorder[i],i);  
     }  
     return helper(0,inorder.length-1,0,inorder.length-1,inorder,postorder,index);  
   }  
   public TreeNode helper(int s1,int e1, int s2, int e2, int[] inorder, int[] postorder, HashMap<Integer,Integer> index){  
     if(s1>e1 || s2>e2) return null;  
     TreeNode root=new TreeNode(postorder[e2]);  
     int ind=index.get(postorder[e2]);  
     root.left= helper(s1,ind-1,s2,ind-1-s1+s2,inorder,postorder,index);  
     root.right=helper(ind+1,e1,ind-s1+s2,e2-1,inorder,postorder,index);  
     return root;  
   }  

Brainstorm:
Can we construct a binary tree from preorder and postorder? 
Answer is no, here is an example: 1;#,2 the preorder and postorder are [1,2] and [2,1] respectively, while for the other tree: 1;2,#, the preorder and postorder are also [1,2] and [2,1], so from preorder and postorder we can't define a unique tree, because we can't differentiate if the node is left child or right child in the example discussed above.