[PAT] A1086 Tree Traversals Again

题目大意

用栈的形式给出一棵二叉树的建立的顺序，求这棵二叉树的后序遍历

tips

string用printf输出：printf(“%s”, str.c_str());

AC代码

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <cstdio> #include <vector> #include<algorithm> #include<stack> using namespace std; vector<int>pre, in; bool space = false; 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 + (i - start) + 1, i + 1, end); if (space == false) { printf("%d", pre[root]); space = true; } else printf(" %d", pre[root]); } int main() { int i, n; scanf("%d", &n); stack<int>st; string op; int number; for (i = 0;i < 2 * n;i++) { cin >> op; if (op == "Push") { scanf("%d", &number); st.push(number); pre.push_back(number); } else {//op=="Pop" in.push_back(st.top()); st.pop(); } } postorder(0, 0, n - 1); return 0; }

另

题目说结点编号1~N，保证了节点值互不相同。 如果在有多个节点的值相同的情况下，之前的代码会输出错误的结果，所以修改后的代码中添加了key作为索引，前中后序中均保存索引值，然后用value存储具体的值。（参考： https://blog.csdn.net/liuchuo/article/details/52181237 ）代码如下：

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <cstdio> #include <vector> #include <map> #include<algorithm> #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; }