个人练习-PAT甲级-1086 Tree Traversals Again

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024

树的遍历，算是重点。二叉树的非递归的中序遍历需要一个栈来辅助，详见https://blog.csdn.net/zhangxiangdavaid/article/details/37115355

想要得到树的结构，要想【什么时候会有新的数据进来？】因为有新数据（节点）进来时，就是要将这个节点X和已知其他节点联系起来的时候。那很明显，这个时刻就是Push的时刻。而根据链接的中序遍历原理，这个X是某个节点的左孩子还是右孩子取决于上一次操作是Push还是Pop，我们用一个last_push记录上次操作是否为Push

节点定义

class Node {
    
public:int left, right;
};

重要的Push时刻，X到底是谁的左/右儿子呢？详细理由之后再补。

        // push Xif (opr[1] == 'u') {
    int X;scanf("%d", &X);if (i > 0) {
    if (last_push)tree[st.back()].left = X;elsetree[cur].right = X;}elseroot = X;st.push_back(X);last_push = true;}

Pop时记录Pop出来的值cur，有可能要在Push时用到。

        // popelse {
    cur = st.back();st.pop_back();last_push = false;}

后续遍历，因为懒就直接递归了

void postTrav(vector<Node>& tree, int head) {
    if (head == 0)return;int left = tree[head].left, right = tree[head].right;if (left != 0)postTrav(tree, left);if (right != 0)postTrav(tree, right);ret.push_back(head);
}

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;class Node {
    
public:int left, right;
};vector<int> ret;void Init(vector<Node>& tree) {
    for (int i = 1; i < tree.size(); i++) {
    tree[i].left = 0;tree[i].right = 0;}
}void postTrav(vector<Node>& tree, int head) {
    if (head == 0)return;int left = tree[head].left, right = tree[head].right;if (left != 0)postTrav(tree, left);if (right != 0)postTrav(tree, right);ret.push_back(head);
}int main() {
    int N;scanf("%d", &N);vector<Node> tree(N + 1);vector<int> st;bool last_push = true;int cur, root;Init(tree);for (int i = 0; i < 2 * N; i++) {
    char opr[5];scanf("%s", opr);// push Xif (opr[1] == 'u') {
    int X;scanf("%d", &X);if (i > 0) {
    if (last_push)tree[st.back()].left = X;elsetree[cur].right = X;}elseroot = X;st.push_back(X);last_push = true;}// popelse {
    cur = st.back();st.pop_back();last_push = false;}}postTrav(tree, root);for (int i = 0; i < ret.size(); i++) {
    if (i != 0)printf(" ");printf("%d", ret[i]);}return 0;
}