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行出栈入栈操作。
输出:输出这棵树的后序遍历。每个值间有个空格隔开。
解题思路:分别将先序遍历和中序遍历用数组存放。然后通过递归得到后序遍历结果。怎么实现已知先序和中序遍历,就能得到后序遍历呢?主要找根节点,从先序遍历的第一个值,就是树的根结点开始递归。我们用样例来分析。
index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
Pre | 1 | 2 | 3 | 4 | 5 | 6 |
In | 3 | 2 | 4 | 1 | 6 | 5 |
后序遍历结果: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;
}