/*

     * 105. Construct Binary Tree from Inorder and preorder Traversal

     * 11.20 By Mingyang

     * 千万不要以为root一定在中间那个点，还是要找一下中间点的位置

     * p.left = construct(preorder, preStart + 1, preStart + (k - inStart),inorder, inStart, k - 1);

     * p.right = construct(preorder, preStart + (k - inStart) + 1, preEnd,inorder, k + 1, inEnd);

     * 难点就在于如何找到这两个起点和终点的index

     */

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        int preEnd = preorder.length - 1;

        int inEnd = inorder.length - 1;

        return construct(preorder, 0, preEnd, inorder, 0, inEnd);

    }

    public TreeNode construct(int[] preorder, int preStart, int preEnd,int[] inorder, int inStart, int inEnd) {

        if (preStart > preEnd || inStart > inEnd) {

            return null;

        }

        int val = preorder[preStart];

        TreeNode p = new TreeNode(val);

        // find parent element index from inorder

        int k = 0;

        for (int i = 0; i < inorder.length; i++) {

            if (val == inorder[i]) {

                k = i;

                break;

            }

        }

p.left = construct(preorder, preStart + 1, preStart + (k - inStart),inorder, inStart, k - 1);
p.right = construct(preorder, preStart + (k - inStart) + 1, preEnd,inorder, k + 1, inEnd);

        return p;

    }