重建二叉树

核心思路：

• 因为二叉树的前序的第一个树必为父结点，而中序中则以该节点为界，左边的则为其左节点，右边的则为其右节点。
• 通过递归重复完成上诉过程就行

代码：

 public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        //先判断pre或in数组是否为空，或者其长度为0，如果是，说明条件不符合或就是空树，直接返回空
        if (pre == null || in == null || pre.length <= 0 || in.length <= 0) {
            return null;
        }
        //如果只有一个节点，也不用往下走，直接返回
        if (in.length == 1) {
            return new TreeNode(in[0]);
        }

        int c = pre[0];

        //寻找父节点
        int mid = 0;
        for (; mid < pre.length; mid++) {
            if (c == in[mid]) {
                break;
            }
        }
        //如果遍历了数组还是没有父节点就返回空
        if (mid == pre.length) {
            return null;
        }

        //构建树
        TreeNode root = new TreeNode(c);                       //根节点

        //结点左边的子树
        int[] midLeft = Arrays.copyOf(in, mid);               //左子树中序
        int[] preLeft = new int[midLeft.length];              //左子树前序
        System.arraycopy(pre, 1, preLeft, 0, preLeft.length);

        int[] midRight = new int[pre.length - mid-1];          //右子树中序
        int[] preRight = new int[midRight.length];             //右子树前序
        System.arraycopy(in, mid+1, midRight, 0, midRight.length);
        System.arraycopy(pre, mid+1, preRight, 0, preRight.length);


        //递归遍历，获取树的左节点和右结点
        root.left = reConstructBinaryTree(preLeft, midLeft);
        root.right = reConstructBinaryTree(preRight, midRight);

        //返回根节点
        return root;

    }