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

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

12. countTrees() Solution (Java)
/**
 For the key values 1...numKeys, how many structurally unique
 binary search trees are possible that store those keys?

 Strategy: consider that each value could be the root.
 Recursively find the size of the left and right subtrees.
*/
public static int countTrees(int numKeys) {
  if (numKeys <=1) {
    return(1);
  }
  else {
    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...
    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
      left = countTrees(root-1);
      right = countTrees(numKeys - root);

      // number of possible trees with this root == left*right
      sum += left*right;
    }

    return(sum);
  }
} 
  

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

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

节点数为 n 的满二叉树的数量是第 n 个加泰罗尼亚数。加泰罗尼亚数字的计算方式为

复杂度为 O(n)。

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

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