105. 从前序与中序遍历序列构造二叉树

难度中等1892
根据前序/后序遍历+中序遍历可以得到一颗树。

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

    public TreeNode create(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight){
        if(preLeft > preRight || inLeft > inRight) return null;
        TreeNode node = new TreeNode(preorder[preLeft]);
        int inIndex = 0;
        for(int i = inLeft; i <= inRight; i++){
            if(node.val == inorder[i]){
                inIndex = i;
                break;
            }
        }
        node.left = create(preorder, preLeft+1, preLeft + inIndex - inLeft, inorder, inLeft, inIndex-1);
        node.right = create(preorder, preLeft + inIndex - inLeft + 1, preRight, inorder, inIndex + 1, inRight);
        return node;
    }

}