L2-011 玩转二叉树 (25 分)-白红宇的个人博客

L2-011 玩转二叉树 (25 分)

发布日期：2021-06-29 22:18:45 浏览次数：2 分类：技术文章

本文共 1246 字，大约阅读时间需要 4 分钟。

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

1 2 3 4 5 6 7

4 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2

/*给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列;pre前序: 4 1 3 2 6 5 7 (root根节点的值) mid中序: 1 2 3 4 5 6 7 (start,end起始索引) index:   0 1 2 3 4 5 6 (根节点索引) 故所得层序遍历序列如下,这层有的子树没有结点，以0显示---> 层序:    4  6  1  7  5  3  0  0  0  0  0  0  0  2 		 0  1  2  3  4  5  6  7  8  9  10 11 12 13其中index,2*index+1,2*index+2的取值范围就是从零开始逐渐递增的;*/#include
   
    #include
    
     #include
     using namespace std;vector
      
        pre,mid;map
       
         level;void level_order(int root,int start,int end,int index){
   	//cout<<" 123 ";	//如果是叶子节点的话，就不做相应的操作; 	if(start>end) return;	int k=start;	while(mid[k]!=pre[root]) k++;	level[index]=pre[root];	/*	因为需要将非叶子节点的左右孩子互换;	将2*index+1放在右子树;	将2*index+2放在左子树;	*/	//左子树; 	level_order(root+1,start,k-1,2*index+2);	//右子树;	level_order(root+1-start+k,k+1,end,2*index+1); }int main(){
   	int n=0,i=0,m=0,j=0,k=0;	cin>>n;	mid.resize(n);	pre.resize(n);	for(i=0;i
        
         >mid[i]; for(i=0;i
         
          >pre[i]; level_order(0,0,n-1,0); vector
          
            temp; for(i=0;i

转载地址：https://dingshijie.blog.csdn.net/article/details/115857354 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：L2-006 树的遍历 (25 分)

下一篇：[Error] ‘nullptr‘ was not declared in this scope解决方案

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章