Leetcode/微软 -- 106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal
Medium
Given inorder and postorder traversal of a tree, construct the binary tree.
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 

思路：post order: last node is root.
Then find root pos in inorder, left side is left subtree(0=isEnd to rindex-1), right side is right subtree (rindex+1 to isStart = len-1).
In left subtree, the root in postorder is at root - (#in right subtree)
In right subtree, the root in postoder  is root-1
Recursively build
 Complexity: Time O(N) , Space O(1)       

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, inorder.length-1, 0, postorder, postorder.length-1);
    }

    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart) {
     if(postStart<0||inEnd > inStart)return null;
     TreeNode root = new TreeNode(postorder[postStart]);
     //find root pos in inorder,can also use hashmap to store pos
     int rindex = 0;
     for(int i=inStart;i>=inEnd;i--){
         if(inorder[i]==postorder[postStart]){
             rindex = i;
             break;
         }
     }
     root.left = buildTree(inorder, rindex-1, inEnd, postorder, postStart-(inStart-rindex)-1);//reverse wrong, locate left subtree root
     root.right = buildTree(inorder,inStart, rindex + 1, postorder, postStart-1);//2nd last is root of right subtree
     return root;
    }
}