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

题目大意：  n(二叉树中结点个数)
　　　　　　假设二叉树中的所有键都是不同的正整数，根据后序遍历和中序遍历求层次遍历

 1 #include <cstdio>
 2 #include <vector>
 3 #include <map>
 4 using namespace std;
 5 vector<int> post, in;
 6 map<int, int> level;
 7 void pre(int root, int start, int end, int index) {
 8     if(start > end) return ;
 9     int i = start;
10     while(i < end && in[i] != post[root]) i++;
11     level[index] = post[root];
12     pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
13     pre(root - 1, i + 1, end, 2 * index + 2);
14 }
15 int main() {
16     int n;
17     scanf("%d", &n);
18     post.resize(n);
19     in.resize(n);
20     for(int i = 0; i < n; i++) scanf("%d", &post[i]);
21     for(int i = 0; i < n; i++) scanf("%d", &in[i]);
22     pre(n-1, 0, n-1, 0);
23     auto it = level.begin();
24     printf("%d", it->second);
25     while(++it != level.end()) printf(" %d", it->second);
26     return 0;
27 }

解法：1、根据后续遍历和中序遍历转化为前序遍历，并给每个结点赋上index变量：因为后序的最后
　　　　一个总是根结点，令i在中序中找到该根结点，则i把中序分为两部分，左边是左子树，右边
　　　　是右子树。因为是输出先序（根左右），所以先打印出当前根结点，然后打印左子树，再打
　　　　印右子树。左子树在后序中的根结点为root – (end – i + 1)，即为当前根结点-(右子树
　　　　的个数+1)。左子树在中序中的起始点start为start，末尾end点为i – 1.右子树的根结点
　　　　为当前根结点的前一个结点root – 1，右子树的起始点start为i+1，末尾end点为end。
　　　2、根据Map的Key按从小到大排序的特性，使用迭代器把Value值打印出来。

1020 Tree Traversals (25分)

原文：https://www.cnblogs.com/i-chase/p/13158074.html