计算所有结构不同的二叉树数量的时间复杂度是多少？

Question

使用这里介绍的方法：http://cslibrary.stanford.edu/110/BinaryTrees.html#java

12. countTrees() 解决方案 (Java)
/**
 对于键值1...numKeys，有多少个结构独特的二叉搜索树可以存储这些键？
策略：考虑每个值都可能是根。
 递归地查找左子树和右子树的大小。
*/
public static int countTrees(int numKeys) {
  if (numKeys <=1) {
    return(1);
  }
  else {
    // 根节点将有一个值，左右两侧的剩余部分将形成自己的子树。
    // 迭代所有可能成为根的值...
    int sum = 0;
    int left, right, root;
for (root=1; root<=numKeys; root++) {
      left = countTrees(root-1);
      right = countTrees(numKeys - root);
// 具有此根的可能树的数量 == left*right
      sum += left*right;
    }
return(sum);
  }
} 

我感觉它可能是n(n-1)(n-2)...1，即n！

如果使用记忆化技术，复杂度是O(n)吗？

- Lawrence Lau

Answer 1

节点数为n的满二叉树个数是第n个卡特兰数。卡特兰数计算方法如下：

这是复杂度为O(n)。

http://mathworld.wolfram.com/BinaryTree.html

http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics

- Robert Harvey

Answer 2

不确定记忆化版本将对查找表进行多少次命中（肯定是超线性的，并且会有函数调用的开销），但是由于数学证明得出结果与第n个卡塔兰数相同，因此可以快速设计出线性时间的表格方法：

    int C=1;
    for (int i=1; i<=n; i++)
    {
        C = (2*(2*(i-1)+1)*C/((i-1)+2));
    }
    return C;

请注意记忆化和表格化之间的区别这里。

- Chandni Verma

Answer 3

对于给定的节点数，计算此算法使用countTrees的调用次数非常容易。经过几次试运行，我发现对于n >= 2，它需要5*3^(n-2)个调用，增长速度比n!慢得多。这个断言的证明留给读者作为练习。:-)

像你建议的那样，记忆化版本只需要O(n)个调用。

顺便说一下，具有n个节点的二叉树的数量等于第n个卡特兰数。计算C_n的明显方法似乎都是线性的，因此记忆化实现countTrees可能是最好的方法。

- Jim Lewis