18. 重建二叉树

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int ps = 0;
        int is = 0;
        int pe = preorder.length-1;
        int ie = inorder.length-1;
        return creatTree(preorder,ps , pe ,inorder,is,ie);
    }
    public TreeNode creatTree(int []preorder,int ps ,int pe ,int []inorder,int is,int ie) {
        if(ps>pe)return null;
        int temp = preorder[ps];
        TreeNode node = new TreeNode(temp);
        int k = 0;
        while(k<inorder.length) {
            if(temp == inorder[k])break;
            k++;
        }
        node.left = creatTree(preorder, ps+1 ,ps+k-is ,inorder,is ,k-1);
        node.right = creatTree(preorder, ps+k-is+1 ,pe ,inorder,k+1 ,ie);
        return node;
    }
}