从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvix0d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
答案参考了评论区大佬。

首先，需要明白，前序遍历二叉树的顺序。其第一个结点必然是根节点，然后若根节点有左子树，其根节点的下一个节点必然为其左子树的根节点。否则，若有右子树，则下一个节点必然为右子树的根节点。（前序是从前往后看，后序从后往前看就可以）
明确这个逻辑就好办了，那么我们如何知道根节点有无左右子树呢？这就需要通过中序遍历顺序来确定了。在中序顺序中，根节点左侧为其左子树，右侧为其右子树。我们只想要知道有没有左右子树即可，所以只需确定中序顺序中根节点的左右两侧的元素个数即可。

1.递归

1.每轮递归返回当前前序序列的根节点，返回后在前序序列中删掉根节点。
2.由中序序列递归其左右子树。
3.递归返回结果连接到当前根节点的左右孩子上。

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        List<Integer> pre = new ArrayList<>();
        List<Integer> in = new ArrayList<>();
        for(int i = 0; i < preorder.length; i++){
            pre.add(preorder[i]);
            in.add(inorder[i]);
        }
        return recursion(pre, in);    
    }
    public TreeNode recursion(List<Integer> pre, List<Integer> in){
        if(in.size() == 0){
            return null;
        }
        int midVal = pre.remove(0);
        TreeNode root = new TreeNode(midVal);
        int mid = in.indexOf(midVal);
        root.left = recursion(pre, in.subList(0, mid));
        root.right = recursion(pre, in.subList(mid + 1, in.size()));
        return root;
    }

2.非递归

截取主集合的操作都可以转换成由双指针指示数组范围。唯一需要注意的就是由于不能在数组中删除元素。所以当前的根节点的左右子树根节点位置需要想办法获取，如果是左子树根，那么就下一位就是，如果是右子树根那么就需要跨过中间的所有左子树的结点。也就是中序序列中的：根位置-当前树起始位置+1

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        return recursion(preorder, inorder, 0, 0, inorder.length - 1);    
    }
    public TreeNode recursion(int[] preorder, int[] inorder, int preCur, int inBegin, int inEnd){
        if(preCur > preorder.length - 1 || inBegin > inEnd){
            return null;
        }
        int midVal = preorder[preCur];
        TreeNode root = new TreeNode(midVal);
        int mid = -1;
        for(int i = 0; i < inorder.length; i++){
            if(inorder[i] == midVal){
                mid = i;
                break;
            }
        }
        root.left = recursion(preorder, inorder, preCur + 1, inBegin, mid - 1);
        root.right = recursion(preorder, inorder, preCur + mid - inBegin + 1, mid + 1, inEnd);
        return root;
    }