题目
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
分析题目
日常查单词环节：postorder and inorder traversal sequences 后序和中序遍历序列
level order traversal sequence 层序遍历序列
根据题意，这是一个已知后序和先序遍历序列求层序遍历序列的题目
先去学习了一下柳神的关于已知后序与中序输出前序
后序中序输出前序
代码
首先说明几个变量
root 根结点的位置（后序） i 根节点的位置（中序）
b 树开始遍历的位置（中序） e 树结束遍历的位置（中序）
后序为左右根，中序为左根右
后序序列中最后一个肯定是树的根结点，从最后一个开始，将中序分成两拨。
左子树遍历的起始点为b, 结束点为i-1，根节点为root-1-(e-i)
右子树遍历的起始点为i+1,结束点为e，根节点为root-1
#include <iostream>
using namespace std;
int post[] = {3, 4, 2, 6, 5, 1};//后序序列
int in[] = {3, 2, 4, 1, 6, 5};//中序序列
void pre(int b, int e, int root)
{
if(b > e)
return;
int i = b;
while(i< e && post[root] != in[i]) i++;
cout << post[root] << " " << i << " " << e << endl;
pre(b, i-1, root-1-(e-i));
cout << "i: " << i << " b: " << b << " e: " << e << " root:" << root << endl;
pre(i+1, e, root-1);
}
int main()
{
pre(0, 5, 5);
return 0;
}
好了学习完成，我们来看这道题，这题是一个已知后序和中序遍历序列求层序遍历序列的题目，思路是一样的。
后序为左右根，中序为左根右
后序序列中最后一个肯定是树的根结点，从最后一个开始，将中序分成两拨。
左子树遍历的起始点为b, 结束点为i-1，根节点为root-1-(e-i)
右子树遍历的起始点为i+1,结束点为e，根节点为root-1
为了输出层序，则另设一个变量index跟踪其层数
代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> post, in, level(100000, -1);
void pre(int root, int b, int e, int index)
{
int i = b;
if(b > e)
return;
while(i < e && post[root]!= in[i]) i++;
level[index] = post[root];
pre(root-1-(e-i), b, i-1, index*2+1);
pre(root-1, i+1, e, index*2+2);
}
int main()
{
int N;
int cnt = 0;
cin >> N;
post.resize(N);
in.resize(N);
for(int i = 0; i<N; i++) cin >> post[i];
for(int i = 0; i<N; i++) cin >> in[i];
pre(N-1, 0, N-1, 0);
for(int i = 0; i<level.size(); i++)
{
if(level[i] != -1)
{
if(cnt!= 0)
cout << " ";
cout << level[i];
cnt++;
}
if(cnt == N)
break;
}
return 0;
}
总结：
柳神太强了，但有个点没弄懂，就是如果用index去记录结点在树中的位置，题目给的边界条件为N<=30，按理说，最大应是2^30，这个数远大于代码里的100000，但还是能够AC了，这个地方没太懂。
这题典型的已知树的其中两个序列，求第三个序列
通过柳神代码里还学会了vector中resize的用法，和初始化一个固定长并填入初始值的方法，这样使得代码看起来更加简洁高效。
每日吹柳神
