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