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

============================================================
传说中正确率比较高的一道题，有0.5哈哈
做起来却发现数据结构概念忘光光，后序遍历什么的一概忘掉了，百度百科了一下终于懂得了..
题目也没什么技巧，给定两种顺序，肯定能排出二叉树的
要求输出层次结构就更好办了…
因为题目简单所以多记下一点，怕自己万一碰到忘掉了。
============================================================
原理：
后序遍历的顺序是L-R-D，后面假定这个输入序列为A序列
中序遍历是L-D-R顺序，假定为B序列
序列遍历时其实是递归的感觉。
也就是说，后序遍历顺序的最后一个节点，肯定是D节点无误（一棵树不会没有根，除非是空树）
所以给定A、B序列，把A序列的最后一个节点放到B序列中，那么B序列就能被分割成左中右三个部分，
中间那个节点，中间节点的左子树、右子树。
于是也成为了个递归的过程，每次分割完成后，把左右字数再找他们对应的D节点（从序列A中看），就能到世界的尽头了。
============================================================
伪代码：

工作队列：W
输入序列：A, B
将B整个队列压入W
while(工作队列非空)
{
    取出工作队列的队首元素（也是一个队列）frontList
    弹出队首元素（c++里面取top()或者front()和pop()是两个过程）
    找出frontList中位于A列最后次序的元素m
    打印m
    将frontList中排在m元素左侧的那些元素组成新列表，压入W队列
    将frontList中排在m元素右侧的那些元素组成新列表，压入W队列
}

==============================================================
代码（高手勿喷，效率较低但是在PAT中耗时0ms,内存占用750k+-）：

#include 
#include 
using namespace std;
int N;
int* A; //后序遍历顺序
int* B; //中序遍历顺序
struct QueueElem
{
	//压到工作队列中的元素（其实也是个队列）
	int capacity;
	int curSize;
	int* elements;
	QueueElem(int _capacity)
	{
		capacity = _capacity;
		curSize = 0;
		elements = new int[capacity];
	}
	void addElem(int e)
	{
		if(curSize >= capacity )
		{
			cerr << "Fail to insert. Size exceeded!" << endl;
			return;
		}
		elements[curSize++] = e;
	}
};
queue W; //工作队列
int findLastOnePos(QueueElem e)
{
	//寻找QueueElem元素中处在A列次序最后的那个元素
	//返回值为该元素在【e列表】中的位置！
	//2层循环效率较低..
	int lastIndexA = -1;
	int lastIndexE = -1;
	for(int i=0; i lastIndexA)
			{
				lastIndexA = posA;
				lastIndexE = i;
				break;
			}
		}
	}
	return lastIndexE;
}
int main()
{
	cin >> N;
	A = new int[N];
	B = new int[N];
	QueueElem orig(N);
	for(int i=0; i>A[i];
	for(int i=0; i>B[i];
		orig.addElem(B[i]);
	}
	///////////
	W.push(orig);
	int count = N;
	while (count--)
	{
		QueueElem qe = W.front();
		W.pop();
		int posM = findLastOnePos(qe);
		cout << qe.elements[posM];
		if( count > 0)
			cout << " ";
		if(posM > 0)
		{
			//有左侧元素
			QueueElem L(posM);
			//左侧元素组成列压栈，务必保持原有顺序！
			for(int i=0; i 1)
		{
			//有右侧元素
			QueueElem R(qe.curSize - posM -1);
			//右侧元素组成列压栈，务必保持原有顺序！
			for(int i=posM +1; i