1020 Tree Traversals （25）

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

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

Sample Output:

4 1 6 3 5 7 2

题意比较清晰，通过中序遍历和后序遍历来找到树的层序遍历，该过程由两部分组成

1.恢复树的结构，通过递归每次生成一个根结点，再找到该结点所在子树的中序序列中的位置，提取出该子树的左右子树，进入下一层递归

2.树恢复后，通过BFS来得到层序遍历序列

个人对树的复原过程理解的不够深，熟练度很低，代码很粗糙，做了很久才做出来，这种数据结构的模拟题还是需要多做才有感觉

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 vector<int> inorder;  //存储中序遍历
 5 vector<int> postorder;  //存储后序遍历
 6 typedef struct BiTnode{
 7     int data;
 8     struct BiTnode *lchild,*rchild;
 9 }node,*tree;
10 tree get_root(int parent,vector<int> v){
11     if (v.empty())
12         return NULL;
13     node *root=new node();   //创建该子树的根节点
14     root->data=parent;
15     vector<int> left,right;   //存储左子树和右子树
16     int parent_index;
17     for(int i=0;i<v.size();++i){
18         //找到父节点在中序遍历中位置
19         if (v[i]==parent){
20             parent_index=i;
21             break;
22         }
23     }
24     for(int i=0;i<v.size();++i){  //划分左右子树
25         if (i<parent_index)
26             left.push_back(v[i]);
27         else if (i>parent_index)
28             right.push_back(v[i]);
29     }
30     vector<int>::iterator it;
31     if (!left.empty())  //存在左子树
32         for (int i=n-1;i>=0;--i){
33             it=find(left.begin(),left.end(),postorder[i]);
34             if (it!=left.end()){
35                 root->lchild=get_root(postorder[i],left);
36                 break;
37             }
38         }
39     if (!right.empty())  //存在右子树
40         for (int i=n-1;i>=0;--i){
41             it=find(right.begin(),right.end(),postorder[i]);
42             if (it!=right.end()){
43                 root->rchild=get_root(postorder[i],right);
44                 break;
45             }
46         }
47     return root;
48 }
49 void BFS(queue<tree> q,node *root){
50     if (q.empty())
51         return;
52     queue<tree> temp;
53     while(!q.empty()){
54         tree p=q.front();
55         if (p!=root)  //将根节点提前输出方便保证最后没有空格
56             cout<<" "<<p->data;
57         if (p->lchild!=NULL)
58             temp.push(p->lchild);
59         if (p->rchild!=NULL)
60             temp.push(p->rchild);
61         q.pop();
62     }
63     BFS(temp,root);
64 }
65 int main(){
66     int temp;
67     cin>>n;
68     for (int i=0;i<n;++i){
69         cin>>temp;
70         postorder.push_back(temp);
71     }
72     for (int i=0;i<n;++i){
73         cin>>temp;
74         inorder.push_back(temp);
75     }
76     node *Bitree=get_root(postorder[n-1],inorder);
77     queue<tree> initial;
78     initial.push(Bitree);
79     cout<<Bitree->data;
80     BFS(initial,Bitree);
81 }