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

题意

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

题解

我们知道若要构成一棵树需要知道这棵树的前序和中序,或者后序和中序。现在我们只有后序那么如何构建这棵树呢。因为二叉排序树的中序遍历就是序列的排序结果,也就是说我们有了这个序列就有了这个序列的中序遍历即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");
}
全部评论

相关推荐

榕城小榕树:1200单休,我去干点啥别的不好
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-04 15:20
牛客61197583...:看到室友一个个没怎么学通过关系直接入职或者接到面试,真的很难受。八股不知道背了多少遍,hot100也刷了1.5遍了,但就是没有面试的机会,唉
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务