美文网首页
2019-03-13 重建二叉树

2019-03-13 重建二叉树

作者: longxingxiu | 来源:发表于2019-03-13 23:31 被阅读0次

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

解答1 :递归实现

    /**
     * @param pre 前序遍历
     * @param in  中序遍历
     * @return 二叉树根节点
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        /*
         * 输入合法性判断, 不能为空,先序和后序长度要一致
         */
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }

        return construct(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    /**
     * @param preArray 前序遍历
     * @param preStart 前序遍历的开始位置
     * @param preEnd   前序遍历的结束位置
     * @param inArray  中序遍历
     * @param inStart  中序遍历的开始位置
     * @param intEnd   中序遍历的结束位置
     * @return 数的根节点
     */
    private TreeNode construct(int[] preArray, int preStart, int preEnd, int[] inArray, int inStart, int intEnd) {
        if (preStart > preEnd) {
            return null;
        }

        // 取前序遍历的第一个数字就是根节点
        int value = preArray[preStart];
        // 在中序遍历中中寻找根节点
        int index = inStart;
        while (index <= intEnd && value != inArray[index]) {
            index++;
        }
        // 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常
        if (index > intEnd) {
            throw new RuntimeException("Invalid Iuput!");
        }

        // 创建当前根节点,并为根节点赋值
        TreeNode node = new TreeNode(value);
        // 左子树大小 = 中序中根节点位置 -中序中起始位置
        int leftTreeSize = index - inStart;

        // 递归调用构建当前节点的左子树
        node.left = construct(preArray, preStart + 1, preStart + leftTreeSize, inArray, inStart, index - 1);
        // 递归调用构建当前节点的右子树
        node.right = construct(preArray, preStart + leftTreeSize + 1, preEnd, inArray, index + 1, intEnd);

        return node;
    }

相关文章

  • LeetCode 每日一题 [42] 重建二叉树

    LeetCode 重建二叉树 [中等] 输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历...

  • Java后端开发算法基础面试题分享,你离大厂也许就差这份面试题!

    一、算法基础 1. 重建二叉树 题目: 输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。 注意: 二叉树中...

  • 重建二叉树

    已知二叉树的前序和中序遍历序列,以此重建二叉树。 重建二叉树,必须知道前序和中序序列,其他组合都不行。 publi...

  • 剑指Offer(四)

    剑指Offer(四) 重建二叉树 题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的...

  • Java日记2018-06-19

    重建二叉树 矩阵中的路径

  • 一题一算法2018-02-06(重建二叉树)

    题目:重建二叉树 题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍...

  • 重建二叉树

    《剑指offer》面试题7:重建二叉树 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前...

  • 重建二叉树

    题目来源:牛客网--重建二叉树 题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序...

  • java中如何实现重建二叉树

    java中如何实现重建二叉树 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和...

  • 2019-03-13 重建二叉树

    题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的...

网友评论

      本文标题:2019-03-13 重建二叉树

      本文链接:https://www.haomeiwen.com/subject/ohxfmqtx.html