在算法比赛或者408数据结构里面可能会出现问n个结点组成的二叉树有多少种不同的形态，因为二叉树不是平衡二叉树也不是排序二叉树，所以组成的情况包含非常多。下面讲解一下如何推断，主要还是利用动态规划的思想。
我们定义f(n)表明结点为n的二叉树的形态数
- 一个结点只有一种情况，记f(1)=1
- 两个结点的二叉树，固定一个结点后，剩下左右子树各有一种情况，f(2)=f(1)*f(1)+f(1)*f(1)
如果有三个结点，我们如果固定两个结点是不太好的，因为两个结点的二叉树有好多种，不便于推理。
我们固定根节点，那么剩下两个结点我们可以分配给左右子树，分别有三种情况
- 左子树两个右子树零个
- 左右子树分别一个
- 右子树两个左子树一个
那么f(3) = f(2)*f(0)+f(1)*f(1)+f(0)*f(2)
那么f(0)是多少呢，没有结点也是一种情况，所以f(0)=1
我们不需要结点增加时候每一个树的组成的具体形状是怎么样的，只是知道往左右子树分配多少个结点，每个结点有多少种组合方式，接着遍历递推就可以了。
那么如果有n个结点，我们可以得到：
f(n) = f(n-1) * f(0)+f(n-2) * f(1)+...+f(0) * f(n-1)
而刚好这个数列正好是卡特兰数，上面式子也就是下面的式子
n个结点组成的二叉树有f(n)种形态
四个结点的二叉树有8!/(4! * 5!)=14种形态
标签：结点,子树,形态,二叉树,多少,组成 From： https://blog.csdn.net/newxiaoou/article/details/139483724