算法标签：

树结构

题解：

1.先还原二叉树形态，后递归 1 首先二叉树的种类数满足卡特兰数，所以有递推关系可得出任意结点的卡特兰数ct[]，根据编号找到它的结点数，和在该结点数下的第几棵树。

2 由编号还原二叉树形态，右子树满足卡特兰数满状态时，左子树移动一下，直到左子树满足它的卡特兰数。

3 递归画图，递归框架，从根节点开始画，第一层传参时，不输出左右括号，其余结点，只要存在就要有右括号,画完左边画’X’画右边 2.对左子树为空，右子树为空，左右子树非空递归 1 一样推出这棵树有多少个节点，以及是当前第几个编号 2 当编号小于ct[结点-1]时，左子树此时为空，往下递归，结点数减一，编号不变 3 当编号大于ct[结点]-ct[结点-1]，右子树为空，递归时所在编号需要减去（左子树为空+左右子树非空）的树的数目，即n-(ct[结点]-ct[结点-1]) 4 左右子树均非空时，先推出右子树的节点数 5 递归子树

#include <iostream>
#include <algorithm>
#define LL long long
#define Pr pair<int, int>
using namespace std;

int n, m;
LL ct[233];
LL cts[233];

void init()
{
    ct[0] = 1;
    cts[0] = 0;
    for (int t = 1; t < 33; t++)
    {
        ct[t] = ct[t - 1] * (4 * t - 2) / (t + 1);
        cts[t] = cts[t - 1] + ct[t - 1];
    }
}

void f(LL x, bool flag = 1)
{
    if (x == 0)
        return;
    LL l, r;
    int pos;
    for (int i = 0;; i++)
    {
        if (x < cts[i])
        {
            pos = i - 1; // 结点
            break;
        }
    }
    l = 0;
    r = pos - 1;
    x -= cts[pos]; // 位于pos结点卡特兰数的第x位
    LL p1 = 0;
    while (x - ct[r] >= 0) // 还原二叉树的形态
    {
        x -= ct[r];
        p1++; // 左子树形态+1
        if (p1 == ct[l])
        {
            l++;
            r--;
            p1 = 0;
        }
    }
    if (flag)
        cout << '(';
    f(cts[l] + p1);
    cout << 'X';
    f(cts[r] + x);
    if (flag)
        cout << ')';
}

int main()
{
    init();
    LL x;
    while (cin >> x)
    {
        if (x == 0)
            break;
        f(x, 0);
        cout << endl;
    }

    return 0;
}