Description：

让你求前序遍历第 $k$ 大的大小为 $n$ 的二叉树的前序遍历，要求中序遍历为 $1,2,3,\dots,n$ 。

$1\leqslant n\leqslant 26$

Solution：

既然是前序遍历，那么最终一定是按照根节点为第一关键字排序的，也就是说如果根节点为 $x$ 的话，那么所有根节点小于 $x$ 的都会排在他前面，设 $C[i]$ 表示卡特兰数，那么这些会有： $$ \sum_{i=1}^{x-1}C[x-1]\times C[n-x] $$ 个排名一定在他前面，既然 $n$ 这么小那么我们就可以暴力把 $x$ 找出来，然后这样就可以计算出左右子树的排名，然后递归下去即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

int n;

ll k;

#define MAXN 27

ll C[MAXN];

void calc(int n,ll k,int delta)

{

	if(n == 0)return;

	int lef = -1;

	ll sum = 0;

	while(true)

	{

		if(sum + C[lef + 1] * C[n - (lef + 1) - 1] < k)

		{

			sum = sum + C[lef + 1] * C[n - (lef + 1) - 1];

			++lef;

		}

		else break;

	}

	++lef;k -= sum;

	putchar(delta + lef + 'a');

	calc(lef,(k - 1) / C[n - 1 - lef] + 1,delta);

	calc(n - lef - 1,(k - 1) % C[n - 1 - lef] + 1,delta + lef + 1);

	return;

}

int main()

{

	scanf("%lld%d",&k,&n);

	C[0] = C[1] = 1;

	for(int i = 2;i <= 30;++i)

	{

		for(int j = 0;j < i;++j)

		{

			C[i] += C[j] * C[i - 1 - j];

		}

	}

	calc(n,k,0);

	cout << endl;

	return 0;

}