106. 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.

思路：

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder==null||postorder==null||inorder.length==0||postorder.length==0){
            return null;
        }

        return construct(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
    }

    public TreeNode construct(int[] inorder, int[]postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd){
        if (inorderStart>inorderEnd || postorderStart>postorderEnd){
            return null;
        }

        int rootVal = postorder[postorderEnd];
        TreeNode root = new TreeNode(rootVal);
        int index = getIndex(inorder,rootVal);

        int inorderStart_left = inorderStart;
        int inorderEnd_left = index-1;
        int postorderStart_left = postorderStart;
        int postorderEnd_left = postorderStart + index - inorderStart - 1;
        root.left = construct(inorder, postorder, inorderStart_left, inorderEnd_left, postorderStart_left, postorderEnd_left);

        int inorderStart_right = index+1;
        int inorderEnd_right = inorderEnd;
        int postorderStart_right = postorderStart + index - inorderStart;
        int postorderEnd_right = postorderEnd-1;
        root.right = construct(inorder, postorder, inorderStart_right, inorderEnd_right, postorderStart_right, postorderEnd_right);

        return root;
    }

    public int getIndex(int[] inorder, int rootVal){
        for (int i=0; i<inorder.length; i++){
            if (inorder[i]==rootVal) return i;
        }
        return -1;
    }
}