9640 - 树的排序

1. 空树编号为 0，只有根节点的树编号为 1；
2. 设 m 为一任意非负整数，那么任意一棵有 m 个节点的树的编号小于任意一棵有 m+1 个节点的树；
3. 设 A,B 是两棵节点数相同的树（A,B 不相同），则 A 编号比 B 小时，一定满足下面两个条件之一（反之亦然）：
   1. A 左子树编号小于 B 左子树编号；
   2. A 左子树编号等于 B 左子树编号（即 A,B 左子树形态相同），且 A 右子树编号小于 B 右子树编号；
4. 编号按照正常的规则，编号应是连续的非负整数，任意一棵树唯一对应一个编号，任意一个非负整数唯一对应一棵树。

（注：上述树均指二叉树）

仅 1 行，为一个整数 n，1\le n\le 500{,}000{,}000。

对于 10\% 的数据，保证树节点个数不超过三个。

仅 1 行，为对应编号为 n 的二叉树。按下列方式输出：

• 如果是一个结点的二叉树，则输出 X；
• 如果二叉树的左、右子树分别为 L 和 R，L,R 的输出形式分别为 L' 和 R'，则输出为 \texttt{(}L'\texttt{)}X\texttt{(}R'\texttt{)}，当左子树为空时，输出为 X\texttt{(}R'\texttt{)}，当左子树为空时 \texttt{(}L'\texttt{)}X。

卡特兰数

湖南省选