墨歆洹 2021-11-23 14:55 采纳率: 66.7%
浏览 20
已结题

中序遍历和先序遍历 创建二叉树,如下代码中,参数preEnd要传入:preStart+i-inStart,这个为什么要减inStart

递归左子树,参数preEnd要传入:preStart+i-inStart,这个为什么要减inStart
递归右子树参数preStart要传入:preStart+i-inStart+1,这个为什么要减inStart


private static TreeNode reConstructBinaryTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd){
        if(preStart>preEnd || inStart > inEnd){ 
            return null;
        }
        TreeNode  treeNode =new TreeNode(pre[preStart]);
        for(int i=inStart;i<=inEnd;i++){
            if(in[i] == pre[preStart]){ 
                treeNode.lchild = reConstructBinaryTree( pre,preStart+1,preStart+i-inStart,in,inStart,i-1);
                treeNode.rchild = reConstructBinaryTree(pre,preStart+i-inStart+1,preEnd,in,i+1,inEnd);
            }
        }
        return treeNode;
    }
  • 写回答

1条回答 默认 最新

  • 钰娘娘 2021-11-25 09:54
    关注

    随便举个例子就可以了:
    前序:1 2 3 4 5
    中序:2 3 1 4 5

    前序可以定根,当前范围的第一个是根,但是不知道后续左子树右子树的长度
    初始状态:
    preStart=0,preEnd=4,inStart=0,inEnd=4

    从前序中找到根是1,然后在中序0到4索引范围,找到索引2的值是2,于是对于中序数组,我们知道(0,1)是左子树(2,3)是右子树,其中,左子树的范围是2个元素,
    那么可以把前序的接下来两个元素,考虑为前序的左子树,其余为右子树,
    表达起来就是:

    int len = i-inStart+1; //i为找到的索引2,左子树长度
    int nextLeftPreEnd = (preStart+1)+( i-inStart+1);//起点+长度-1=终点,等价于prevStart+i-inStart;
    int nextRightPreStart = nextLeftPreEnd+1;//其实题目那么写有点迷茫了,前序顺序就是【根,左子树,右子树】,所以排除掉左,紧接着后续就是右
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 12月2日
  • 已采纳回答 11月25日
  • 创建了问题 11月23日

悬赏问题

  • ¥15 PADS Logic 原理图
  • ¥15 PADS Logic 图标
  • ¥15 电脑和power bi环境都是英文如何将日期层次结构转换成英文
  • ¥20 气象站点数据求取中~
  • ¥15 如何获取APP内弹出的网址链接
  • ¥15 wifi 图标不见了 不知道怎么办 上不了网 变成小地球了
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部