acwing:1576. 再次树遍历

打卡一道有意义的题。

题签：

通过使用栈可以以非递归方式实现二叉树的中序遍历。

例如，假设遍历一个如下图所示的 66 节点的二叉树（节点编号从 11 到 66）。

则堆栈操作为：push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop()。

我们可以从此操作序列中生成唯一的二叉树。

你的任务是给出这棵树的后序遍历。

输入格式

第一行包含整数 NN，表示树中节点个数。

树中节点编号从 11 到 NN。

接下来 2N2N 行，每行包含一个栈操作，格式为：

• Push X，将编号为 XX 的节点压入栈中。
• Pop，弹出栈顶元素。

输出格式

输出这个二叉树的后序遍历序列。

数据保证有解，数和数之间用空格隔开，末尾不能有多余空格。

数据范围

1≤N≤301≤N≤30

输入样例：

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

输出样例：

3 4 2 6 5 1

 思路：

一开始没思路，感觉很奇怪，但是看到有人指出非递归遍历的二叉树push过程其实就是先序遍历，pop过程其实就是中序遍历，这么一来那就无脑上板子就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=50;
int n;
int a[N],b[N];
struct tree{
    int l,r;
    int v;
}p[N];
int cnt,idx;
stack<int> stk;

int built(int al,int ar,int bl,int br){
    if(al>ar){
        return 0;
    }
    int r=a[al];
    int k=0;
    while(a[al]!=b[k]){
        k++;
    }
    int len=k-bl;
    p[r].v=r;
    p[r].l=built(al+1,al+len,bl,bl+len);
    p[r].r=built(al+len+1,ar,bl+len+1,br);
    return r;
}
void print(int x){
    if(p[x].l){
        print(p[x].l);
    }
    if(p[x].r){
        print(p[x].r);
    }
    cout<<p[x].v<<" ";
    
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n;i++){
        string str;
        int x;
        cin>>str;
        if(str=="Push"){
            cin>>x;
            stk.push(x);
            a[++cnt]=x;
        }else{
            b[++idx]=stk.top();
            stk.pop();
        }
        
    }
    built(1,n,1,n);
    print(a[1]);
    
}