PAT-A-1086 报告Bug

[boqiang-li]

您好：
在A-1086题中，题目并没有说所有节点的值互不相同。因此，在有多个节点的值相同的情况下，您的代码会输出错误的结果。
虽然一开始，我也是这么写的 ： P

例如，测试数据：

测试用例:
19
Push 4
Push 11
Push 7
Push 12
Pop
Pop
Pop
Push 14
Push 17
Pop
Pop
Push 6
Push 18
Pop
Push 8
Pop
Pop
Push 4
Pop
Pop
Push 11
Push 16
Push 11
Push 12
Pop
Push 2
Pop
Pop
Pop
Push 7
Push 4
Pop
Pop
Push 12
Pop
Pop
Push 11
Pop

对应输出应该为:

12 7 17 8 18 4 6 14 11 2 12 11 4 12 7 16 11 11 4

你的输出为:

12 7 17 8 18 6 14 11 11 16 4 7 2 11 12 12 11 4 4

[boqiang-li]

我在您的代码上简单修改了一下。
添加了key作为索引。前中后序中均保存索引值。然后用value存储具体的值。
最后ac代码如下：

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
vector<int> pre, in, post,value;
void postorder(int root, int start, int end) {
	if (start > end) return;
	int i = start;
	while (i < end && in[i] != pre[root]) i++;
	postorder(root + 1, start, i - 1);
	postorder(root + 1 + i - start, i + 1, end);
	post.push_back(pre[root]);
}
int main() {
	int n;
	scanf("%d", &n);
	char str[5];
	stack<int> s;
	int key=0;
	while (~scanf("%s", str)) {
		if (strlen(str) == 4) {
			int num;
			scanf("%d", &num);
			value.push_back(num);
			pre.push_back(key);
			s.push(key++);
		}
		else {
			in.push_back(s.top());
			s.pop();
		}
	}
	postorder(0, 0, n - 1);
	printf("%d", value[post[0]]);
	for (int i = 1; i < n; i++)
		printf(" %d",value[post[i]]);
	return 0;
}

[boqiang-li]

另外，其实也可以最后不保存postorder的，在post.push_back(pre[root]);的时候，直接输出即可。
设置一个flag，用于标记是否是第一个数。
也就是说，可以写成

//之前设置bool flag=false;

	if (flag)
		cout << ' ';
	cout << value[pre[root]];
	flag = true;

[liuchuo]

已修改为您的代码并署名，感谢～

[boqiang-li]

我又被翻牌了，开熏。