PAT-A-1086 Tree Traversals Again (25)

题目

题目链接 重新遍历二叉树 用栈的形式给出一棵二叉树的建立的顺序,求这棵二叉树的后序遍历. ## 输入 每个输入包括一个测试用例。

第一行是一个正整数N(<=30)表示树中的节点总数(节点从1~N进行编号)。然后是2N行,每行描述一种堆栈操作,比如Push X,其中X是被压入堆栈的节点的索引;或Pop,表示从堆栈中弹出一个节点。 ## 输出 在一行中输出相应的树的后续遍历序列。数字之间由空格隔开。 # 解题 ## 思路分析 1. push的顺序正好对应前序。 2. pop出来的顺序正好对应中序。

Tips

  1. 特别注意:数字可以有重复。所以要加一个索引。
  2. 经过实测,不加索引也能通过PAT的测试,但是无法通过牛客网的测试。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<vector>
#include<string>
#pragma warning(disable:4996)
using namespace std;

int n;
string temp;
vector<int>pre, mid,value;
bool flag = false;
void post(int root, int start, int end)
{
if (start > end)
return;
int i = start;
while (i<end&&mid[i]!=pre[root])
{
i++;
}
post(root + 1, start, i - 1);
post(root + 1 + i - start, i + 1, end);
if (flag)
{
cout << ' ';
}
cout << value[mid[i]];
flag = true;
}

void solution()
{
cin >> n;
int num, top = 0;
int stack[31] = {0};
int c1 = 0;
for (int i = 0; i < n*2; i++)
{
cin >> temp;
if (temp=="Push")
{
cin >> num;
value.push_back(num);
pre.push_back(c1);
stack[top++]=c1++;
}
else if (temp=="Pop")
{
mid.push_back(stack[--top]);
}
}
post(0, 0, n - 1);
}

int main()
{
freopen("2.txt", "r", stdin);
solution();
system("pause");
return 0;
}

测试数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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