[牛客算法总结]：重建二叉树

标签：

二叉树、DFS、先序遍历、中序遍历、递归

题目：

给定节点数为 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

输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：{1,2,3,4,#,5,6,#,7,#,#,8}
说明：
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示

示例2

输入：[1],[1]
返回值：{1}

反思：个人思考

由于二叉树的先序遍历：根左右、中序遍历：左根右可可以得出：
1、根节点为pre[0]
2、中序遍历中跟位置左边为左子树、右边为右子树
3、通过不断递归、我们可以得出每一个节点

具体思路
// root index = 1
// 先序遍历：[1,2,4,7,3,5,6,8]
// 中序遍历：[4,7,2,1,5,3,8,6]
// 具体思路是：先通过先序遍历的特点找到跟节点，然后通过跟节点来找到根节点在
// 中序遍历中的位置，然后根据中序遍历的特点(左根右)，root左边的就是左子树的个数
// root右边的就是右子树的个数，根据这个特点来通过本方法找到root.left，root.right
// 再通过递归，找到每一个节点。

用到的知识点：

二叉树、DFS、先序遍历、中序遍历、递归、Arrays.copyOfRange()：左包右不包

代码：代码内容

    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        if (pre == null || pre.length == 0) return null;
        // 构建具体的树根
        TreeNode root = new TreeNode(pre[0]);

        // 通过先序遍历和中序遍历来找到根节点在中序遍历的位置
        int index = findRootIndexInOrder(pre, vin);

        // 通过递归构建左子树
        root.left = reConstructBinaryTree(
                        Arrays.copyOfRange(pre, 1, index + 1),
                        Arrays.copyOfRange(vin, 0, index)
                    );
        // 通过递归构建右子树
        root.right = reConstructBinaryTree(
                         Arrays.copyOfRange(pre, index + 1, pre.length),
                         Arrays.copyOfRange(vin, index + 1, vin.length)
                     );

        return root;
    }

    public int findRootIndexInOrder(int[] pre, int[] vin) {
        for (int i = 0; i < vin.length; i++) {
            if (pre[0] == vin[i]) return i;
        }
        return 0;
    }