题目地址：从前序与中序遍历序列构造二叉树

解题思路

解题思路来自左程云老师的算法课新手班第六节

先序，中序都可以展示出树的结构，先序是头左右，中序是左头右。

由先序可以得出树的头节点，因为题目上数据条件上说，均无重复元素。

说明，只需要在中序中遍历到和先序数组第一个元素值相同的元素，它的前面就是左树，后面就是右树，在先序中，也可以根据这个左树的个数去得到左树和右树的下标范围。

所以：定义find，遍历数组，在in（中序数组）中找到头

int find=L2;
while (in[find]==pre[L1]){
    find++;
}

根据这个find就可以知道这个头节点下方左树和右树的规模，左树规模为 [L1，find-1]，右树规模为[ find+1,R2 ].

而我们的目标是建立一颗完整的树，也就是每个节点都必须建立，

先建立出头节点

TreeNode head = new TreeNode(pre[L1]);

接着去考虑头节点的左右树，这时就需要考虑递归

我们需要去新创建一个方法，将先序数组，中序数组，都传进去。

建立好头节点之后，该节点的左右树，左树将左树在先序和中序的范围传入，右树将右树在先序和中序的范围传入如此接着建立。

head.left = build(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
head.right = build(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);

边界条件判断

如果传入的数组为空，或者两个数组长度不一致，那么直接返回空

if (preorder == null || inorder == null || preorder.length != inorder.length) {
   return null;
}

如果L1=R1，说明该节点下方为空，直接返回该节点即可

if (L1 == R1) {
    return head;
}

假如L1>R1,说明该节点下方并非左右都有

比如先序为[1,2,3],中序也是[1,2,3]。那么树的结构应该为1右树为2，2右树为3，但是这样在调用方法时，

build(pre, L1 + 1, L1 + find - L2, in, L2, find - 1)，find为0，L1+1（也就是下一次的L1）为1，L1+find-L2（也就是下一次的R1）为-1，1>-1，所以返回null

if(L1>R1){
   return null;
}

完整代码

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    public TreeNode build(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
        if(L1>R1){
            return null;
        }
        int find = L2;
        while (in[find] != pre[L1]) {
            find++;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        head.left = build(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
        head.right = build(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
        return head;
    }