剑指offer系列之四:重建二叉树-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

剑指offer系列之四:重建二叉树

简介:

题目描述

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

在完成代码之前,我自己分析了一下如何根据前序遍历和中序遍历的结果构建一棵二叉树。首先,根据二叉树遍历的性质,由前序遍历的结果序列可知该二叉树的根节点是1,在根据中序遍历的结果可是根节点1的左子树包含的结点是4、7、2,右子树包含的节点是5、3、8、6。现在考虑左子树中节点4、7、2,由于这三个节点在前序遍历的结果是2、4、7,那么2必然是这三个节点组成的子树的根节点,再回到中序遍历的结果4、7、2,那么可以判断出4是2的左孩子,7是4的右孩子;同理可以对右子树进行判断。这样,画出的二叉树是这样的:

构建的二叉树

自然,我们可以分析判断过程写出构建二叉树的完整代码:

package com.rhwayfun.offer;

public class ConstructBinaryTree {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return constructCore(pre,0,pre.length - 1,in,0,in.length - 1);
    }

    private TreeNode constructCore(int[] pre,int startPreOrder, int endPreOrder, int[] in,int startInOrder, int endInOrder) {
        //根据前序遍历找到根节点的值
        int rootValue = pre[startPreOrder];
        TreeNode rootNode = new TreeNode(rootValue);
        rootNode.left = null;
        rootNode.right = null;

        //只有一个结点,那么该节点就是根节点,直接返回
        if(startPreOrder == endPreOrder){
            if(startInOrder == endInOrder && pre[startPreOrder] == in[startInOrder]){
                return rootNode;
            }
        }

        //根据中序遍历的结果找到根节点
        int rootOfInOrder = startInOrder;
        while(rootOfInOrder <= endInOrder && in[rootOfInOrder] != rootValue){
            rootOfInOrder++;
        }

        //异常处理
        if(rootOfInOrder == endInOrder && in[rootOfInOrder] != rootValue){
            return null;
        }

        //计算左子树的长度
        int leftSubTreeLen = rootOfInOrder - startInOrder;
        //根据左子树的长度计算前序遍历结果中左子树的最后一个结点的下标
        int leftIndexOfPreOrderEnd = startPreOrder + leftSubTreeLen;
        //重建左子树
        if(leftSubTreeLen > 0){
            rootNode.left = constructCore(pre, startPreOrder + 1, leftIndexOfPreOrderEnd, in, startInOrder, rootOfInOrder - 1);
        }
        //重建右子树
        if(leftSubTreeLen < endPreOrder - startPreOrder){
            rootNode.right = constructCore(pre, leftIndexOfPreOrderEnd + 1, endPreOrder, in, rootOfInOrder + 1, endInOrder);
        }
        return rootNode;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode root = new ConstructBinaryTree().reConstructBinaryTree(pre, in);
        System.out.println(root);
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章
最新文章
相关文章