1086 Tree Traversals Again (25分)

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.

Figure 1

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 the line.

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

题目描述：题目给定一个二叉树的中序遍历，不过，这个中序遍历要用过出栈入栈的方法得到，出栈的顺序就是这棵二叉树的中序遍历，而入栈的顺序就是先序遍历(这个有一丢丢难看出来哈，画画图就知道了)。给出先序和中序遍历，求后序遍历。

输入：第一行n为二叉树的节点数，接下来2*n行出栈入栈操作。

输出：输出这棵树的后序遍历。每个值间有个空格隔开。

解题思路：分别将先序遍历和中序遍历用数组存放。然后通过递归得到后序遍历结果。怎么实现已知先序和中序遍历，就能得到后序遍历呢？主要找根节点，从先序遍历的第一个值，就是树的根结点开始递归。我们用样例来分析。

后序遍历结果：3 4 2 6 5 1

1）递归一开始，root=0，inl=0，inr=n-1=5，这些传入函数的值分别是根节点在先序遍历Pre中的索引位置，中序遍历的左右索引边界。

2）递归的退出口是非常重要的，要想好放在哪。这里就是当inl大于inr时，递归结束。

3）while循环得到的是根节点在中序遍历中的位置，用i来标记。

4）接着分别找到先序遍历中，当前根节点的左右子结点索引，充当递归的根节点索引。为什么找索引，知道索引，那么值也就很容易得到啦

5）左子结点直接root+1就行；右子节点需要计算一下，式子为root+(i-inl)+1，i-inl是左子树值的个数，这里需要把他们排除了，再加一，就得到右子节点的索引了。

6）为什么post_back写在最后面，题目求的是后序遍历嘛。放在while循环后面得到先序遍历，放在两个get_post之间得到中序遍历。

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 100;
int in[maxn], pre[maxn];
vector<int> post;
void get_post(int root, int l, int r){
	if(l>r) return ;
	int i = l;
	while(i<=r&&pre[root]!=in[i]) i++;
	get_post(root+1,l,i-1);
	get_post(root+i-l+1,i+1,r);
	post.push_back(pre[root]);
}
int main()
{
	string str;
	int c1=0, c2=0, c3=0, k;
	stack<int> s; 
	cin >> n;
	for(int i=0; i<2*n; i++){
		cin >> str;
		if(str=="Push"){
			cin >> k;
			pre[c1++] = k;
			s.push(k);
		}
		else{
			in[c2++] = s.top();
			s.pop();
		}
	}
	get_post(0, 0, n-1);
	for(int i=0; i<post.size(); i++){
		if(i) printf(" ");
		printf("%d", post[i]);
	}
	return 0;
}