Unique Binary Search Trees II(Medium)

题目：Given n, generate all structurally unique BST's (binary search trees) that store values 1...n. (输出二叉查找树的所有组合)

要求出所有组合的问题，一般用dfs；如果要求总数，用dp。

还有值得注意的技巧是，当begin>end时，要往ret AL里面添加null， 使得每个AL里面至少有一个元素（null） 。这样可以避免判断只有左区间或只有右区间的情况。

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

  TreeNode(int x) {
    val = x;
    left = null;
    right = null;
  }
}

public List<TreeNode> generateTrees(int n) {
  return dfs(1, n);
}

private List<TreeNode> dfs(int start, int end) {
  List<TreeNode> result = new ArrayList<TreeNode>();
  if (start > end) {
    result.add(null);
    return result;
  }

  for (int i = start; i <= end; i++) {
    // generate left and right sub tree
    List<TreeNode> leftTree = dfs(start, i - 1);
    List<TreeNode> rightTree = dfs(i + 1, end);
    // link left and right sub tree to root(i)
    for (TreeNode lnode: leftTree) {
      for (TreeNode rnode: rightTree) {
        TreeNode root = new TreeNode(i);
        root.left = lnode;
        root.right = rnode;
        result.add(root);
      }
    }
  }

  return result;
}