这道题也不算难，我依然采用map来进行处理 ，代码依旧较短
机翻
1、条件准备
我这里采用数组模拟栈，tt指向栈顶；
map的键存结点值，后面数对存左右子树的结点值
head存头节点的值
#include<iostream>
#include<map>
#include<string>
using namespace std;int stk[100],tt=-1;
map<int,pair<int,int>> m;
int head;
主函数先是加快输入输出，然后输入结点数量，
调用inordertraval生成这样一棵树，也就是中序遍历的逆过程
再调用aftertraval后序遍历输出
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int num;cin>>num;inordertraval(num);aftertraval(head);return 0;
}
2、inordertrava函数
循环遍历进行操作，n个结点有2*n个操作。
用字符串判断是push还是pop。
如果是push，则用f存一下之前同样的位置有没有存结点。
然后将当前结点存进来，如果i==1，则为头结点，存入head.
那么如何连接这些结点呢，我们来分析一下，如果上一个结点左子树为空则连接到该结点左子树。
因为（栈中）上一个结点左子树为空还没弹出栈，则目前连的结点一定是它的左结点。
如果上一个结点左子树连了，则该节点要连之前该位置结点的右子树。
为什么呢？
因为如果要连上一个结点右子树，则该节点应该被弹出，而现在没弹出，相悖了。
而之前该位置结点已经弹出了，证明其左子树遍历完了，该遍历它右子树了，
所以连它的右结点即可。
pop就简单了，tt--即可。
void inordertraval(int n)
{n *= 2;for (int i = 1; i <= n; i++){string operation;cin >> operation;if (operation == "Push"){int f = stk[++tt];cin >> stk[tt];if (i == 1)head = stk[tt];if (i && m[stk[tt - 1]].first == 0)m[stk[tt - 1]].first = stk[tt];else m[f].second = stk[tt];}elsett--;}
}
3、aftertraval函数
使用递归实现后续遍历，f的左右是控制输出格式，保证最后无多余空格。
如果该节点不为空，则递归左子树，再递归右子树，然后输出该结点。
int f = 1;
void aftertraval(int node)
{if (node){aftertraval(m[node].first);aftertraval(m[node].second);if (f){cout << node;f = 0;}elsecout << ' ' << node;}
}
4、总结
这个题并不难，map我也只是当作一种结构体在用，并且能find的结构体，较为方便。
完整代码如下：
#include <iostream>
#include <map>
#include <string>
using namespace std;int stk[100], tt = -1;
map<int, pair<int, int>> m;
int head;void inordertraval(int n)
{n *= 2;for (int i = 1; i <= n; i++){string operation;cin >> operation;if (operation == "Push"){int f = stk[++tt];cin >> stk[tt];if (i == 1)head = stk[tt];if (i && m[stk[tt - 1]].first == 0)m[stk[tt - 1]].first = stk[tt];else if (i && m[f].second == 0)m[f].second = stk[tt];}elsett--;}
}int f = 1;
void aftertraval(int node)
{if (node){aftertraval(m[node].first);aftertraval(m[node].second);if (f){cout << node;f = 0;}elsecout << ' ' << node;}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int num;cin >> num;inordertraval(num);aftertraval(head);return 0;
}
