设n个节点的二叉树有f(n)种
N个节点,其中1个为根节点,则剩下有n-1个节点,这n-1个节点可以:
0个作为根节点的左子树(1种方法),n-1个节点作为根节点的右子树(f(n-1)种方法)
1个节点作为左子树(1种方法),n-2个节点作为右子树(f(n-2)种方法)
2个节点作为左子树(f(2)种方法),n-3个节点作为右子树(f(n-3)种方法)
以此类推:把这些情况全部加起来:
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(1)
其中f(0) = f(1) = 1
这个数叫做卡特兰数,具体计算方法可百度之
温馨提示:答案为网友推荐,仅供参考