Description
构造n个(2<=n<=20)叶结点的的完全二叉树(完全二叉树意味着每个分支结点都有2个儿子结点),有多少种构造方法?
注意:不改变n个结点的相对顺序,左右儿子不调换.
例如:
4个叶子节点A1,A2,A3,A4，可构造出如下完全二叉树，共5种。
再例如:5个叶子结点,A1,A2,A3,A4,A5，可构造出如下若干种完全二叉树形状,像这样的完全二叉树共有14种.
Input
输入n,表示构造的完全二叉树有n个叶结点(2<=n<=20).
Output
输出构造的完全二叉树的种类.
Sample Input
5
Sample Output
14
Hint
把所有叶节点从左到右编上号：1，2，…，n。
无论怎样构造的完全二叉树，根节点左边的左子树和右边的右子树又都是完全二叉树，
那么n个节点的完全二叉树构造方法数等于左子树的构造方法数乘以右子树的构造方法数，
且要列举所有可能的左子树和右子树情况，而后相加。假设左子树的叶子为1，…，i。
右子树的叶子就是：i+1，…，n。
设n个叶子的完全二叉树构造方法数为Total(n)。Total(n)的递归公式如下,这是Catalan数：
Total(n) = for i=1 to n-1 sum(Total(i) * Total(n-i)) if n>=2
Total(n)=1 if n=1
考虑到计算Total(n)时，所有小于规模n的Total(n-1)，…，Total(1)都可能被计算多次，
存在大量重复计算的问题。因此比较好的方法是对i从2到n，边计算Total(i)，边用表记录下来，
即备忘录的方法，时间复杂度为O(n^2) 。
- 1
- 2
前往页