P205 用 1~n 生成二叉搜索树

描述#

这个题目说的是，给你一个整数 n，你要用 1 到 n 这 n 个数字去生成所有可能的二叉搜索树，然后将它们返回。

比如说，给你的 n 是 3，1/2/3 这 3 个数字总共可以构成 5 棵不同的二叉搜索树。如下所示：
1     1     2     3     3
\     \   / \   /     /
2     3 1   3 1     2
\   /         \   /
3 2           2 1
因此，你要返回这 5 棵二叉搜索树。

相关视频：二叉搜索树的数量

代码#

public class AlgoCasts {
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private TreeNode cloneTree(TreeNode root) {
    if (root == null) return null;
    TreeNode newRoot = new TreeNode(root.val);
    newRoot.left = cloneTree(root.left);
    newRoot.right = cloneTree(root.right);
    return newRoot;
  }

  private List<TreeNode> genTrees(int low, int high) {
    if (low > high) return Collections.singletonList(null);
    if (low == high) return Collections.singletonList(new TreeNode(low));
    List<TreeNode> result = new ArrayList<>();

    for (int i = low; i <= high; ++i) {
      List<TreeNode> lefts = genTrees(low, i-1);
      List<TreeNode> rights = genTrees(i+1, high);
      for (TreeNode left: lefts) {
        for (TreeNode right: rights) {
          TreeNode root = new TreeNode(i);
          root.left = cloneTree(left);
          root.right = cloneTree(right);
          result.add(root);
        }
      }
    }
    return result;
  }

  // Time/Space: O(4^n / n^(3/2))
  public List<TreeNode> generateTrees(int n) {
    if (n < 1) return Collections.emptyList();
    return genTrees(1, n);
  }

}