美文网首页
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;
        }
    

    相关文章

      网友评论

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

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