| 解答： |
直接枚举出答案自然是可行，但有更简单的方法，那就是递推。我们记fn为结点数为n的二叉树的种数：当二叉树的左子树结点个数为0时,有f0×fn−1种方案；当左子树结点个数为1时,有f1×fn−2种方案；当左子树结点个数为2时,有f2×fn−3种方案；……；当左子树结点个数为n-1个时,有fn−1×f0种方案。由此可得
fn=∑(i=0,n-1)fi×fn−1−i
这就是著名的卡特兰数,关于这条公式可以参见一下百度百科的catalan。
求得这个公式之后就可以代入求解了,最后求得答案是42种。 |