PAT A1086 Tree Traversals Again
从题目上来看，是一道树题？
原题如下
题目大意
一个中序二叉树遍历可以借用栈而采用一种不迭代的方法。
就是已知树的先序、中序求后序。
输入：
首先输入树的节点数：整数N，后面2N行分别表示栈的操作
输出对应树的后续遍历。
自己的想法
典型的已知先序、中序求后序的问题。
答案反馈
错误1
没有考虑节点的值一样的情况。
（其实主要不是这个原因，是因为我后序遍历函数写错了，我这个憨批T–T
void Post(int prel, int prer, int inl, int inr) {
if (prel > prer||inl>inr)return;
int k;
for (k = inl; k <= inr; k++) {
if (in[k] == pre[prel])break;
}
int num = k - inl;
Post(prel + 1, prel + num, inl, k - 1);
Post(prel + num + 1, prer, k + 1, inr);
//原来错误的写成了：
//Post(prel + 1, prel + k, inl, k - 1);
//Post(prel + k + 1, prer, k + 1, inr);
//就是num错写为k了T--T
post.push_back(pre[prel]);
}
AC
AC代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<set>
#include<queue>
#include<map>
#include<stack>
using namespace std;
stack<int> temp;
vector<int> in, pre, post, value;
struct node {
int data;
node* lchild, *rchild;
};
void Post(int prel, int prer, int inl, int inr) {
if (prel > prer||inl>inr)return;
int k;
for (k = inl; k <= inr; k++) {
if (in[k] == pre[prel])break;
}
int num = k - inl;
Post(prel + 1, prel + num, inl, k - 1);
Post(prel + num + 1, prer, k + 1, inr);
post.push_back(pre[prel]);
}
int main() {
int n;
cin >> n;
int key = 0;
for (int i = 0; i < 2*n; i++) {
string str;
cin >> str;
if (str == "Push") {
int t;
cin >> t;
temp.push(key);
value.push_back(t);
pre.push_back(key++);
}
else if (str == "Pop") {
in.push_back(temp.top());
temp.pop();
}
}
Post(0, n - 1, 0, n - 1);
//postorder(0, 0, n - 1);
for (int i = 0; i < post.size(); i++) {
if (i != 0)cout << ' ';
cout << value[post[i]];
}
cout << endl;
return 0;
}
结语
感觉我的主题“刷题之路”要改为“见证憨批之路”了
今天小雨，心情也不太好，今天接触到了一些消息感觉保研之路没有以往想象那么顺，果然原来盲目自信了，加油吧！