https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

递归：我们从序列 1 ..n 中取出数字 i，作为当前树的树根。于是，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。通过递归构建所有的子树。

public List<TreeNode> generateTrees(int n) {
    if(n==0) return new ArrayList<TreeNode>();
    return createTree(1,n);
}
//每次递归应该返回可能的子树列表
List<TreeNode> createTree(int start,int end){
    List<TreeNode> list=new ArrayList<>();
    if(start>end){
        list.add(null);
        return list;
    } 
    for(int i=start;i<=end;i++){
        List<TreeNode> leftList=createTree(start,i-1);
        List<TreeNode> rightList=createTree(i+1,end);
        //将左右子树连接
        for(TreeNode left:leftList){
            for(TreeNode right:rightList){
                TreeNode root=new TreeNode(i);
                root.left=left;
                root.right=right;
                list.add(root);
            }
        } 
    }
    return list;
}

---