algorithm - 生成从 1 到 n 的所有二叉搜索树

Question

我遇到了以下问题:

给定一个正整数 n，生成节点为 1、2、...、n 的所有二叉搜索树。

例如，给定 3，得到:

我正在做以下事情:

Generate all the permutations of the sequence (1, 2, ..., n).
For each permutation p:
    Create a tree t.
    For each number n in p:
        Insert n into t.
    If t has not yet been generated, keep it. <-- Expensive Operation

但是，这种方法很慢，因为会生成重复的树(对于 n = 3，(2, 1, 3) 和 (2, 3, 1) 生成相同的树)，我需要确保它们不会被保留.有人会指出我采用更快的方法吗？

Answer 1

这是没有重复的伪代码(但是你仍然需要很多空间，因为树生成的数量很高)。

TreeList void genAllBST(int high,int low) {

  if(high>=low) {
      currList = []
      for(int i=low;i<=high;i++) {
          curr = new Node(i);
          leftList = genAllBST(i-1,low);
          rightList = genAllBST(high,i+1);
          TreeList c = connect(curr,leftList,rightList);  
          currList.add(c);
      }

     return(currList);

  }

   return(null);
}

genAllBST(n,1);