L2-006 树的遍历 (25 分)-白红宇

L2-006 树的遍历 (25 分)

阅读量：1908 次

发布时间：2019-04-26

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

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

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

输出格式：

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

输入样例：

2 3 1 5 7 6 4

1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

/*需要用vector来存储后序遍历和中序遍历,因为post，mid这两个的大小都已经预先知道，故可以使用resize()方法开辟空间;level层序遍历需要存储多少个数据并不知道，故不能预先开辟空间，可以使用map映射，好处是，不需要想vector容器那样，使用中括号赋值之前需要预先resize()方法一下，而map映射不需要这样操作，其实用将level定义成vector也是可以的，不会出现段错误。后序: 2 3 1 5 7 6 4	(root)中序: 1 2 3 4 5 6 7 (start,end) index:0 1 2 3 4 5 6	(index)层序: 4 1 6 0 3 5 7 0 0 2      0 1 2 3 4 5 6 7 8 9*/#include
   
    #include
    
     #include
     using namespace std;vector
      
        post,mid;map
       
         level;//需要定义成map集合对象，这样就不需要预先开辟内存空间; void level_order(int root,int start,int end,int index){
   	if(start>end) return;	int k=start;	while(mid[k]!=post[root]) k++;	level[index]=post[root];	level_order(root-1-end+k,start,k-1,2*index+1);	level_order(root-1,k+1,end,2*index+2);} int main(){
   	int n=0,i=0,j=0,m=0;	cin>>n;    post.resize(n);    mid.resize(n);	for(i=0;i
        
         >post[i]; for(i=0;i
         
          >mid[i]; level_order(n-1,0,n-1,0); vector
          
            temp; int cnt=0; for(i=0;i