重建二叉树(根据先序遍历(或者后序遍历)和中序遍历重建二叉树)

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。重建二叉树(根据先序遍历(或者后序遍历)和中序遍历重建二叉树),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

先序遍历和中序遍历

1、先序遍历的结果中第一个元素一定是根节点
2、先序遍历结果= 根节点+左子树先序结构+右子树先序结果
3、中序遍历结果= 左子树的中序结果+根节点+右子树的中序结果

在这里插入图片描述

根据上图,3为根节点,根据中序遍历9是3的左子树而且只有一个节点,先序中9后面的20就是3的右子树的根节点,然后再看中序遍历,15在20的左侧7在20右侧,得15是20的左子树7是20的右子树。最后构建出的树如下图:
在这里插入图片描述
代码思路:
注:中序遍历数组中根节点的左边都是左子树的节点,根节点右边都是右子树节点
在这里插入图片描述
1、设置变量inedx 方便从preorder数组中从0号下标开始获取节点。
2、判断inedx的合法性,防止我们在最终的递归途中数组越界异常。
3、中序遍历中根结点可以作为一道分界线,左边是他的左子树结点,右边是右子树结点,所以一开始的inorderLeft 为0 而inorderRight为中序遍历数组的长度。
4、根结点就是先序遍历的第一个结点,构建根结点,然后index++(方法中index只加一次是因为在preorder数组中index下标的元素只可能是左结点或者右结点)
5、构建根结点的左子树,(在此之前我们要在中序遍历中找到根结点元素的下标pos),我们知道 中序遍历的序列组成可以表示为 :左子树结点+根结点+右子树结点 所以,根结点的左结点一定在pos之前。
6、然后我们进行递归进行判断inorderLeft 和inorderRight(就是上一个方法传来的pos值)的合法性,只要inorderLeft不是大于等于inorderRight 就说明在根结点下标的左边有元素,也就是说根结点的左子树不为空。
7、构建该结点然后再次进行递归判断,直到根结点的左子树的根结点建立完。此时就要建立根节点的子树、此时传入的inorderLeft为pos+1和一开始的inorderRight,然后进行递归处理,只要 inorderLeft不是大于等于inorderRight 就说明在根结点下标的右边有元素,也就是说明有右子树,之后进行构建。

    //preorder这个数组和inorder长度相同
    //用index记录访问到哪个节点,记录在preorder中访问到哪个元素
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder){
        index = 0;
        //借助buildTreeHelper方法进行递归
        //加入一对参数表示当前子树对应的中序遍历结果的区间。
        return buildTreeHelper(preorder,inorder,0,inorder.length);
    }
    //[inorderLeft,inorderRight)表示当前这个子树的中序遍历区间
        private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int inorderLeft, int inorderRight) {
        if(inorderLeft >= inorderRight){
            //中序遍历区间为空,当前子树为空树
            return null;
        }
        if(index >= preorder.length){
            //先序中的所有元素都访完毕
            return null;
        }
        //根据index取出当前树的根节点的值,并构造根节点
            TreeNode newNode = new TreeNode(preorder[index]);
        //知道根节点后,需要根据根节点,在中序遍历结果中找到左右子树的范围
            //找出当前节点在中序结果中的位置,位置确定,左右子树位置就确定了
            //左子树对应的中序区间[inorderLeft,pos)
            //右子树对应的中序区间[pos+1,inorderRight)
            int pos = find(inorder,inorderLeft,inorderRight,newNode.val);//在中序遍历中找到节点的下标
            index++;//只++一次
            newNode.left = buildTreeHelper(preorder,inorder,inorderLeft,pos);
            newNode.right = buildTreeHelper(preorder,inorder,pos+1,inorderRight);
            return newNode;
    }
    private int find(int[] inorder, int inorderLeft, int inorderRight, int val) {
        for(int i = inorderLeft;i < inorderRight; i++){
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }

后序遍历和中序遍历

1、后序遍历的结果中最后个元素一定是根节点
2、后序遍历结果= 左子树后序结构+根节点+右子树后序结果
3、中序遍历结果= 左子树的中序结果+根节点+右子树的中序结果

在这里插入图片描述
后序遍历为9-》15-》7-》20-》3
后序遍历结果倒置3-》20-》7-》15-》9 相当于一个“镜像”先序,先根节点再右子树再左子树
所以先对后序遍历的数组逆序,之后对上述的代码进行修改先进行右子树再进行左子树即可。

在这里插入图片描述

private int index = 0;
    public TreeNode buildTree(int[] inorder, int[] posorder){
        index = 0;
        int[] posorder1 = new int[posorder.length];
        for(int i = 0; i < posorder.length; i++){
            posorder1[i] = posorder[posorder.length-i-1];
        }
        return buildTreeHelper(posorder1,inorder,0,inorder.length);
    }
    private TreeNode buildTreeHelper(int[] posorder1, int[] inorder, int inorderLeft, int inorderRight) {
        if(inorderLeft >= inorderRight){
            return null;
        }
        if(index >= posorder1.length){
            return null;
        }
        TreeNode newNode = new TreeNode(posorder1[index]);
        int pos = find(inorder,inorderLeft,inorderRight,newNode.val);
        index++;//只++一次
        newNode.right = buildTreeHelper(posorder1,inorder,pos+1,inorderRight);
        newNode.left = buildTreeHelper(posorder1,inorder,inorderLeft,pos);
        return newNode;
    }
    private int find(int[] inorder, int inorderLeft, int inorderRight, int val) {
        for(int i = inorderLeft;i < inorderRight; i++){
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/152997.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!