Description：

给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个。

$1\leqslant n \leqslant10^5$

Solution：

首先如果把这棵树先建出来，然后对他求前序遍历，得到的序列就是要求的序列，因为父亲必须在儿子之前出现在序列里，而前序遍历能保证先进入左子树。

但是二叉查找树直接暴力建树的时间复杂度是 $O(n^2)$ 的，因为可能成为一个长长的链，如果我们把每个数字出现的位置看作它的第二个权值的话，那么整棵树关于第一个权值是一个二叉查找树，关于第二个是一个小根堆，所以这其实是一个笛卡尔树，按照笛卡尔树的方式建树就得到了桶排 $O(n)$ 复杂度的做法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct num

{

	int v,p;

}g[MAXN];

bool cmp_v(num a,num b){return a.v < b.v;}

int s[MAXN],top = 0;

struct node

{

	int lc,rc;

	int val,prio;

}t[MAXN];

int root;

void dfs(int rt)

{

	if(rt == 0)return;

	printf("%d ",t[rt].val);

	dfs(t[rt].lc);

	dfs(t[rt].rc);

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&g[i].v);

		g[i].p = i;

	}

	sort(g + 1,g + 1 + n,cmp_v);

	top = 0;

	for(int i = 1;i <= n;++i)

	{

		t[i].prio = g[i].p;t[i].val = g[i].v;

		while(top != 0 && t[s[top]].prio > t[i].prio)

		{

			t[i].lc = s[top];

			--top;

		}

		if(top == 0)root = i;

		t[s[top]].rc = i;

		s[++top] = i;

	}

	dfs(root);

	puts("");

	return 0;

}