题目的大意是：进行一系列的操作push,pop。来确定后序遍历的顺序
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of t
Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
3 4 2 6 5 1
思路：push过程就是前序遍历，pop过程就是中序遍历，再写一个根据前序和中序遍历确定后序遍历的算法。
2.取先序序列中的第一个元素，该元素为根结点
3.根据根结点在中序序列中查找根结点的位置，从而得到该树左子树结点个数（L）与右子树的结点个数（R）
4.在后序序列数组中，第0到第L个元素为左子树，第L+1到第L+R个元素为右子树，最后一个元素为根结点
#include<cstdio>
#include<stack>
#include<iostream>
#include<string>
using namespace std; #define MAX 30
int preOrder[MAX];
int inOrder[MAX];
int postOrder[MAX]; //根据前序和中序划分，来确定后序遍历。前序的第一个数字为根结点，
//找到根结点root在中序数组位置，中序数组中root左边为根结点左子树，右边为右子树
void Solve(int preL,int inL,int postL,int n){
if(n==)return;
if(n==){
postOrder[postL]=preOrder[preL];
}
int root=preOrder[preL];
postOrder[postL+n-]=root;
int i,R,L;
for(i=;i<n;i++){
if(root==inOrder[inL+i])break;
}
L=i,R=n-i-; //L为左子树结点数目，R为右子树结点数目
Solve(preL+,inL,postL,L); //确定后序数组中根结点root左边的排列顺序
Solve(preL+L+,inL+L+,postL+L,R);
} int main(){
int n;
for(int i=;i<MAX;i++){
preOrder[i]=;
inOrder[i]=;
postOrder[i]=;
}
stack<int> s;
cin>>n;
string str;
int data;
int index=,pos=;
for(int i=;i<*n;i++){
cin>>str;
if(str=="Push"){ //push代表前序遍历
cin>>data;
s.push(data);
preOrder[index++]=data;
}else if(str=="Pop"){ //pop为中序遍历
inOrder[pos++]=s.top();
s.pop();
}
}
Solve(,,,n);
for(int i=;i<n;i++){
if(i>)printf(" ");
printf("%d",postOrder[i]);
}
return ;
}