PTA 树的遍历

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

输入格式：

输入第一行给出一个正整数

输出格式：

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

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2
解题思路：dfs建树,前序中序的建树可以看我前面发的玩转二叉树
菜鸡的成长史 ^-^

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int Hou[50],Zh[50],n;
 4 struct Node
 5 {
 6     int data;
 7     Node *left,*right;
 8 };
 9 Node *dfs(int hl,int hr,int zl,int zr)
10 {
11     if(hl>hr) return NULL;
12     Node *head=new Node;
13     head->data=Hou[hr];  //后序的右边为根节点
14     int weizhi,geshu;
15     for(int i=0;i<n;i++)
16     {
17         if(Zh[i]==Hou[hr]){
18             weizhi=i;break;    //找出根在中序的位置
19         }
20     }
21     geshu=zr-weizhi;  //中序的右边有多少个节点
22     head->left=dfs(hl,hr-geshu-1,zl,weizhi-1);
23     head->right=dfs(hr-geshu,hr-1,weizhi+1,zr);
24     return head;
25 }
26 void bfs(Node *head)
27 {
28     int flag=0;
29     queue<Node*> que;
30     Node *p=head;
31     que.push(head);
32     while(!que.empty())
33     {
34         p=que.front(),que.pop();
35         if(flag!=0) cout << " ";
36         cout << p->data,flag=1;
37         if(p->left!=NULL) que.push(p->left);
38         if(p->right!=NULL) que.push(p->right);
39     }
40     cout << endl;
41 }
42 int main()
43 {
44     ios::sync_with_stdio(false);
45     cin>>n;
46     for(int i=0;i<n;i++) cin>>Hou[i];
47     for(int i=0;i<n;i++) cin>>Zh[i];
48     Node *root=dfs(0,n-1,0,n-1);
49     bfs(root);
50     return 0;
51 }

View Code