105. Construct Binary Tree from Preorder and Inorder Traversal

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

思路：

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

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

    public TreeNode construct(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
        if (preorderStart>preorderEnd||inorderStart>inorderEnd){
            return null;
        }

        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);
        int index = getIndex(inorder,rootVal);

        int preorderStart_left = preorderStart+1;
        int preorderEnd_left = preorderStart+index-inorderStart;
        int inorderStart_left = inorderStart;
        int inorderEnd_left = index-1;
        root.left = construct(preorder,inorder,preorderStart_left,preorderEnd_left,inorderStart_left,inorderEnd_left);

        int preorderStart_right = preorderStart+index-inorderStart+1;
        int preorderEnd_right = preorderEnd;
        int inorderStart_right = index+1;
        int inorderEnd_right = inorderEnd;
        root.right = construct(preorder,inorder,preorderStart_right,preorderEnd_right,inorderStart_right,inorderEnd_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;
    }
}