美文网首页剑指offer java版
【剑指offer】问题7:重建二叉树

【剑指offer】问题7:重建二叉树

作者: 蛋花汤汤 | 来源:发表于2019-02-14 00:05 被阅读0次

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

    先上代码。

       /**
         * 重建二叉树
         */
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            return core(pre, in, 0,pre.length - 1, 0, in.length - 1);
        }
    
        public TreeNode core(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
            // 根节点(前序遍历的第一个节点)
            int rootVal = pre[preStart];
            TreeNode root = new TreeNode(rootVal);
            // 找到根节点在中序遍历数组中的位置
            int rootIndexIn = inStart;
            for(;rootIndexIn <= inEnd; rootIndexIn++){
                if(in[rootIndexIn] == rootVal)
                    break;
            }
            // 计算左子树的长度
            int leftLen = rootIndexIn - inStart;
            // 计算右子树的长度
            int rightLen = inEnd - rootIndexIn;
            if(leftLen > 0){
                // 存在左子树
                // 找到左子树的中序遍历数组
                int leftInStart = inStart;
                int leftInEnd = leftInStart + leftLen - 1;
                // 找到左子树的前序遍历数组
                int leftPreStart = preStart + 1;
                int leftPreEnd = leftPreStart + leftLen - 1;
                // 构建左子树
                root.left = core(pre,in,leftPreStart, leftPreEnd, leftInStart, leftInEnd);
            }
    
            if(rightLen > 0){
                // 存在右子树
                // 找到右子树的中序遍历数组
                int rightInStart = rootIndexIn + 1;
                int rightInEnd = rightInStart + rightLen - 1;
    
                // 找到右子树的前序遍历数组
                int rightPreStart = preEnd - rightLen + 1;
                int rightPreEnd = preEnd;
    
                // 构建右子树
                root.right = core(pre, in, rightPreStart, rightPreEnd, rightInStart, rightInEnd);
            }
    
            return root;
        }
    

    关于树的问题很多都可以使用递归的方式解决,只要将一般化的处理过程想清楚,再把返回条件搞好,基本就可以。本题已知二叉树的前序遍历和中序遍历结果,找出根节点的值,然后再根据这个值找出左子树和右子树对应的前序和中序遍历结果,就可以进行递归编程了。此题比较麻烦的子树数组的界限问题,处理好这个问题,递归也就不会出错了。
    详细的解题流程在注释里已经比较清楚,不再赘述。

    相关文章

      网友评论

        本文标题:【剑指offer】问题7:重建二叉树

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