PAT1127 如何根据后序遍历中序遍历建树？

原题链接：PAT1127

解析：本题要求按s形层次遍历二叉树，如此一来建树就成了首要目的，然后再利用栈的先进后出的特性来s形遍历。于是难点主要放在了如何根据后序遍历和中序遍历来建立一颗二叉树。

代码实例：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
const int maxn = 50;
int post[maxn],in[maxn];
struct Node{
	int data;
	Node *ls,*rs;
	int level;
};
Node* BuildTree(Node *root,int l1,int r1,int l2,int r2,int level){
	if(l1 > r1)	return NULL;
	root = new Node();
	root->data = post[r1];
	root->level = level;
	int p = l2;
	while(in[p] != post[r1])	p++;
	int len = p-l2;
	root->ls = BuildTree(root->ls,l1,l1+len-1,l2,l2+len-1,level+1);
	root->rs = BuildTree(root->rs,l1+len,r1-1,l2+len+1,r2,level+1);
	return root;
}
void printTree(Node *root){
	if(root->ls != NULL)	printTree(root->ls);
	cout << root->data << " ";
	if(root->rs != NULL)	printTree(root->rs);
	return;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 0;i < n;i++)	scanf("%d",&in[i]);
	for(int i = 0;i < n;i++)	scanf("%d",&post[i]);
	Node* root;
	root = BuildTree(root,0,n-1,0,n-1,0);
	//printTree(root);
	stack<Node> sa,sb;
	printf("%d",root->data);
	if(root->rs != NULL)	sa.push(*root->rs);
	if(root->ls != NULL)	sa.push(*root->ls);
	while(sa.size() || sb.size()){
		while(sa.size()){
			Node a = sa.top();
			sa.pop();
			printf(" %d",a.data);
			if(a.level%2 == 0){
				if(a.rs != NULL)	sb.push(*a.rs);
				if(a.ls != NULL)	sb.push(*a.ls);
			}else{
				if(a.ls != NULL)	sb.push(*a.ls);
				if(a.rs != NULL)	sb.push(*a.rs);
			}
		}
		while(sb.size()){
			Node b = sb.top();
			sb.pop();
			printf(" %d",b.data);
			if(b.level%2 == 0){
				if(b.rs != NULL)	sa.push(*b.rs);
				if(b.ls != NULL)	sa.push(*b.ls);
			}else{
				if(b.ls != NULL)	sa.push(*b.ls);
				if(b.rs != NULL)	sa.push(*b.rs);
			}
		}
	}
	return 0;
}