pat甲级1020中序后序求层序
1020?Tree Traversals (25)(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 void pre(int root,int begin,int end) 2 { 3 if (begin > end) return; 4 cout << post[root] << " "; 5 int p; 6 for (p = begin; p <= end; p++) 7 { 8 if (in[p] == post[root]) 9 break; 10 } 11 pre(root - end + p - 1,begin,p - 1); 12 pre(root - 1,p + 1,end); 13 } 后序中最后一个元素为跟,找出跟在中序中的位置就可以确定左右子树的节点个数,然后就可以递归的去求解。 这个题是求层序遍历,开始使用的构造树然后再广度优先搜索的方法,比较繁琐。后来看柳婼的博客发现使用数组的方法构造树比较方便。 若当前根的下标为i,则左节点下标为 2 * i + 1,右节点下标为 2 * i + 2。 1 #include <iostream> 2 #include <vector> 3 #include <math.h> 4 using namespace std; 5 6 vector<int> post,in,level(100000,-1); 7 void getLevel(int root,int end,int index); 8 9 int main() 10 { 11 int N,i; 12 cin >> N; 13 post.resize(N); 14 in.resize(N); 15 for (i = 0; i < N; i++) 16 cin >> post[i]; 17 for (i = 0; i < N; i++) 18 cin >> in[i]; 19 getLevel(N - 1,0,N - 1,0); 20 int cnt = 0; 21 for (int i : level) 22 { 23 if (i != -1) 24 { 25 if (cnt > 0) 26 cout << " "; 27 cnt++; 28 cout << i; 29 if (cnt == N) 30 break; 31 } 32 } 33 return 0; 34 } 35 36 void getLevel(int root,int index) 37 { 38 if (begin > end) return; 39 level[index] = post[root]; 40 int p; 41 for (p = begin; p <= end; p++) 42 { 43 if (in[p] == post[root]) 44 break; 45 } 46 getLevel(root - end + p - 1,p - 1,2 * index + 1); 47 getLevel(root - 1,p + 1,end,2 * index + 2); 48 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |