【题解】二叉排序树的先序

题意

给你一棵二叉排序树的后序序列，求这棵树的先序序列。

题解

我们知道若要构成一棵树需要知道这棵树的前序和中序，或者后序和中序。现在我们只有后序那么如何构建这棵树呢。因为二叉排序树的中序遍历就是序列的排序结果，也就是说我们有了这个序列就有了这个序列的中序遍历即1到n。那么就可以用中序和后序去构建这二叉树了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int post[N];
void dfs(int x,int l,int r)
{
    if(l>r)
        return;
    printf("%d ",post[x]);
    dfs(x-1-r+post[x],l,post[x]-1);
    dfs(x-1,post[x]+1,r);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&post[i]);
    dfs(n,1,n);
    printf("\n");
}