/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return recursion(postorder.length-1,0,inorder.length-1,inorder,postorder);
}
private TreeNode recursion(int postLast,int inStart,int inEnd,int[] inorder, int[] postorder){
if(inStart > inEnd || postLast<0){
return null;
}
TreeNode root = new TreeNode(postorder[postLast]);
int inIndex = 0;
for(int i = inStart;i<=inEnd;i++){
if(inorder[i]==root.val){
inIndex = i;
}
}
root.left = recursion(postLast-(inEnd-inIndex)-1,inStart,inIndex-1,inorder,postorder);
root.right = recursion(postLast-1,inIndex+1,inEnd,inorder,postorder);
return root;
}
}
