1. 递归

1.1 分析

1. pre[0]是root,在in中找到root的位置
2. 找到root位置后，根据其index确定左右子树的pre和in的范围, 递归
   
   
   图片转载自 https://blog.nowcoder.net/n/7131c90ce3214472887b0f2f6652f5a7
3. 注意，Arrays.copyOfRange()的后两个参数确定数组边界，是左闭右包"[)"

   1.2 代码

   import java.util.Arrays;
   public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0){
            return null;
        }
        //pre[0]是root,在in中找到root的位置
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){
            //找到root位置后，根据其index确定左右子树的pre和in的范围,递归
            //Arrays.copyOfRange()的后两个参数确定数组边界，是左闭右包"[)"
            if(in[i] == pre[0]){
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,1+i),
                Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),
                Arrays.copyOfRange(in,i+1, in.length));
                break;
            }
        }
        return root;
    }
   }

   1.3 复杂度

   空间：O（n）
   时间：O(n)