一本“奇怪的数学书”上记载了这样一种正整数→二叉树的一一对应。
每棵二叉树用一个只含有的字符串X,(,)表示,每个X表示一个节点。每个X左右都可以有或没有一对括号,这对括号内的字符串表示这个节点的左子树或者右子树。每对括号内的子树以递归的满足上述定义。
比如说字符串(X)X(X(X))表示的就是这样一颗二叉树
树与数的对应法则是这样的:
每棵树唯一对应一个数字,每个数唯一对应一棵树;
只有一个节点的树是1;
树的节点个数越多数字大;
节点数相同的树比较左子树,左子树完全相同的比较右子树。
可见这个比较是递归进行的。
我们可以画出前几个树:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| | | | | | | | | | |
X | X | X | X | X | X | X | X | X | X | X |
| \ | / | \ | \ | / \ | / | / | \ | \ | \ |
| X | X | X | X | X X | X | X | X | X | X | ......
| \ | / | | \ | / | \ | \ | / \ |
| X | X | | X | X | X | X | X X |
| \ | / |
| X | X |
现在你的任务很简单,只需要把数转化为对应的树,用字符串形式输出即可。