105. Construct Binary Tree from

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

（图片来源https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
）

Thoughts

1. 前序：确定root；
2. 中序：确定左、右子树的范围/长度

非递归

public TreeNode buildTree(int[] preOrder, int[] inorder) {
        return helper(0, 0, inorder.length - 1, preOrder, inorder);
    }


    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preOrder, int[] inOrder) {
        if(preStart > preOrder.length-1 || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preOrder[preStart]);  // 根结点
        int inIndex = 0; // Index of current root in inorder
        for(int i=inStart; i<=inEnd; i++) {
            if(inOrder[i] == root.val) {
                inIndex = i;
            }
        }


        root.left = helper(preStart+1, inStart, inIndex-1, preOrder, inOrder);

        // 长度：delta = (inIndex - 1) - inStart + 1 = inIndex - inStart ;
        //      s = preStart + 1 + delta = preStart + inIndex - inStart + 1
        root.right = helper(preStart+inIndex-inStart+1, inIndex+1,
                inEnd, preOrder, inOrder);

        return root;
    }