算法（4）重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

  /**
     * 首先拿到这个问题的时候 我也尝试着画出 自己的二叉树来找规律 发现不行
     * 既然不行 那么我们就行给出的条件里找答案
     * 首先我们自己画出一个自己的二叉树，然后写出来前序和中序数组 肉眼看不出来规律
     * 那么我们就根据 前序的特性 很容易能找到根节点就是中左右的中
     * 那么在中序数组中这个数字的左边就是左子树群体，右边是右子树群体
     * 然后我们发现这个左右群体在我们的前序中也能很明显的区别开只是个体顺序不同
     * 那么我们也能在前序数组中分出中左右。
     * 既然我们分出了整体的中左右，那么个体的中左右采用递归就可以了。
     *
     * @param pre 前序 中左右
     * @param in  中序 左中右
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        //根节点
        TreeNode root = new TreeNode(pre[0]);
        if (pre.length <= 1 || in.length <= 1) {
            return root;
        }

        int index_root = 0;
        //在中序数组中寻找到根节点的位置
        for (int i = 0; i < in.length; i++) {
            if (in[i] == root.val) {
                index_root = i;
                break;
            }
        }

        int[] left_in = new int[index_root];
        int[] right_in = new int[in.length - index_root - 1];
        int[] left_pre = new int[index_root];
        int[] right_pre = new int[pre.length - index_root - 1];


        System.arraycopy(in, 0, left_in, 0, left_in.length);
        System.arraycopy(in, left_in.length + 1, right_in, 0, right_in.length);
        System.arraycopy(pre, 1, left_pre, 0, left_pre.length);
        System.arraycopy(pre, left_pre.length + 1, right_pre, 0, right_pre.length);
        //左子树
        root.left = reConstructBinaryTree(left_pre, left_in);
        //右子树
        root.right = reConstructBinaryTree(right_pre, right_in);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

最后草图一枚，价值千万：

草图