· 定理
n个节点二叉树形态种类数为Cat (n)。
· 证明
很难通过简单递推得到答案，因为会产生重复的情况。
一般我们使用二叉树都是通过递归，故考虑从递归处得到启发。
对于任意n个节点的二叉树，它的左右子节点个数是可以被枚举的 —— 1 + (n - 1) / 2 + (n - 2)...
所以可以通过递归实现，故ƒn = ƒ1 * ƒn - 1 + ƒ2 * ƒn - 2 + ...
满足卡特兰数条件，故定理成立。
原文：https://www.cnblogs.com/Colythme/p/9735678.html