如何找到可能的二叉树拓扑排列的数量？

Question

给定二进制树节点(X)写入方法的数量,该方法返回具有X个节点的二叉树的随机排列的数量.

例子:

X = 1:1

     o

X = 2:2

     o    o
   o        o

X = 3:5

        o    o          o     o        o
      o        o      o         o    o   o
    o            o      o     o

我结束了:

    public static int numOfPerms(int numOfNodes) {
       if (numOfNodes<=2 && numOfNodes > 0) {
           return numOfNodes;
       }
       int res = 1;
       for (int i=1; i<=numOfNodes; i++) {
           res = res*(4*i-1)/(i+1);
       }
       return res;
    } 

我希望在这里分享更好的解决方案.

Answer 1

我认为加泰罗尼亚数字可以统计你的树木(参见组合学中有关应用的部分).它们形成了一个众所周知的序列,通常由这种递归关系定义:

这种复发经常出现在关于树或递归结构的枚举问题中,因此它得到了很好的研究.我链接的维基百科条目为第n个加泰罗尼亚数字提供了许多有用的封闭形式表达式,即

所有这些都适用于代码实现,并且比任何递归方法都快得多.