完全二叉树构造方法计数

"完全二叉树的构造方法计数" 完全二叉树是一种特殊的二叉树，其中每一层（除了可能的最后一层）都是完全填充的，而最后一层的所有节点都尽可能地靠左排列。给定一定数量的叶节点，我们需要找出能够构建这种特定结构的不同方式。在描述中提到的例子中，4个叶节点可以构建5种不同的完全二叉树，而5个叶节点则可以构建14种。 题目要求我们计算具有n个叶节点的完全二叉树的构造方法数。这个问题与Catalan数有关，Catalan数在计算机科学中有多种应用，包括括号匹配、分治问题和二维格子路径等。对于n个叶节点的完全二叉树，其构造方法数可以通过以下递归公式计算： \[ \text{Total}(n) = \sum_{i=1}^{n-1} \text{Total}(i) \times \text{Total}(n-i) \quad (n \geq 2) \] 并且，当n=1时，\(\text{Total}(1) = 1\)。这个递归公式反映了完全二叉树的特性，即一个完全二叉树可以分解成一个左子树和一个右子树，这两个子树都是完全二叉树。 在提供的代码中，`NumOfTree`函数实现了这个递归公式的动态规划解决方案。它使用一个数组`h`来存储每个小规模问题的解，避免了重复计算。数组的索引`i`对应于`i+1`个叶节点的完全二叉树的构造方法数。初始化`h[0]`和`h[1]`分别为1，然后从`i=2`开始迭代，对于每个`i`，遍历所有可能的子树大小`j`，并将它们的组合数累加到`h[i]`。 在主函数`main`中，程序读取用户输入的叶节点数`n`，调用`NumOfTree`函数计算结果，并打印出来。由于使用了动态规划，该算法的时间复杂度为\( O(n^2) \)，这在n的范围为2到20的情况下是可行的。 完全二叉树的构造方法数问题是一个经典的动态规划问题，它涉及到递归和Catalan数的概念，通过高效地存储中间结果，可以避免重复计算并得到正确的解决方案。