牛客J27重组二叉树

给定节点数为 n 请重建二叉树并返回其头结点。 如输入前序遍历序列{1、2、4、7、3、5、6、8}和中序遍历序列{4、7、2、1、5、3、8、6}，则重建如下图所示。

提示: 1.vin.length == pre.length 2.pre 和 vin 均无重复元素 3.vin所有出现的元素都出现在这里 pre里 4.只需返回根结点，系统将自动输出整棵树进行答案比较 数据范围：n \le 2000n≤2000，节点的值 -10000 \le val \le 10000?10000≤val≤10000 要求：空间复杂性 O(n)O(n)，时间复杂度 O(n)O(n)

前序遍历(根左右):[1] 后续遍历(左根右)[4，7，2]，[1]

子序遍历(根左右): [2],4,7 子后序遍历(左根右) 4.7.[2](无右儿童)

对于前序遍历的第一个节点1，中序遍历处于中间位置，两侧对应左右子树。

三个步骤：

1.首先要找到当前的元素节点，即pre中的第一个 2.然后在中序遍历中找到它的左右子树(这里表现为前序数组和中序数组的分割操作)，以构建它的左右子树。 3.最后将左右子树分别放入重构函数中。

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) { 
                return Reorgtrees(pre, 0, pre.length - 1, vin, 0, vin.length - 1);     }      public TreeNode Reorgtrees(int[] pre, int left, int right, int[] vin, int left1, int right1) { 
                if (left >= pre.length || left > right || left1 >= vin.length || left1 > right1) { 
                    return null;         }         TreeNode node = new TreeNode(pre[left]);          ///输入中序数组边界的遍历         for(int i = left1; i<= right1; i++){ 
       
            if(pre[left] == vin[i]){ 
       
                //重构左子树，注意边界条件
                node.left = Reorgtrees(pre,left+1,left+i-left1,vin,left1,i-1);
                //重构右子树，注意边界条件
                node.right = Reorgtrees(pre,left+i+1-left1,right,vin,i+1,right1);
            }
        }

        return node;

    }