【题目】
distinct 不同的
postorder 后序的
inorder 中序的
sequence 顺序；次序；系列
traversal 遍历
题目大意：给出二叉树的后序遍历和中序遍历，求层次遍历。
【思路】
方法一：参见《算法笔记》
方法二：无需建树。参见 https://blog.csdn.net/liuchuo/article/details/52137796
【AC代码】
方法一：
1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 #define N 32 5 struct node { 6 int data; 7 node *lchild, *rchild; 8 }; 9 int in[N], post[N]; 10 int n; 11 node* tree(int postleft, int postright, int inleft, int inright) 12 { 13 if (postleft > postright || inleft > inright) 14 { 15 return NULL; 16 } 17 node* root = new node; 18 root->data = post[postright]; 19 int i, k; 20 for (i = inleft; i <= inright; i++) 21 if (in[i] == post[postright]) 22 break; 23 k = i - inleft; 24 root->lchild = tree(postleft, postleft + k - 1, inleft, i - 1); 25 root->rchild = tree(postleft + k, postright - 1, i + 1, inright); 26 return root; 27 } 28 void level(node* root) 29 { 30 int output = 0;//记录输出了多少个数，因为最后一个数输出之后没有空格。 31 queue<node*>q; 32 q.push(root); 33 while (!q.empty()) 34 { 35 node* tnode = q.front(); 36 q.pop(); 37 cout << tnode->data; 38 output++; 39 if (output < n) 40 cout << " "; 41 if (tnode->lchild != NULL)q.push(tnode->lchild); 42 if (tnode->rchild != NULL)q.push(tnode->rchild); 43 } 44 } 45 int main() 46 { 47 cin >> n; 48 int i; 49 for (i = 0; i < n; i++) 50 cin >> post[i]; 51 for (i = 0; i < n; i++) 52 cin >> in[i]; 53 node* root = tree(0, n - 1, 0, n - 1); 54 level(root); 55 return 0; 56 }
