给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
示例：来源：力扣
输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
- 二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
- 这道题主要参考链接是：从构建单棵树到构建所有树，清晰易懂的递归思路。
- 构建一颗二叉搜索树
构建一颗二叉搜索树很简单，只需要选择一个根结点，然后递归去构建其左右子树。
public TreeNode createBinaryTree(int n){
return helper(1, n);
}
//二叉搜索树左大于右则表示空，在二叉搜索树中右大于左
public TreeNode helper(int start, int end){
if(start > end)
return null;
// 这里可以选择从start到end的任何一个值做为根结点，
// 这里选择它们的中点，实际上，这样构建出来的是一颗平衡二叉搜索树
int val = (start + end) / 2;
TreeNode root = new TreeNode(val);
root.left = helper(start, val - 1);
root.right = helper(val + 1, end);
return root;
}
要构建多颗二叉树，问题就在于如何选择不同的根节点，以构建不同的树和子树。
// 选择所有可能的根结点
for(int i = start; i <= end; i++){
TreeNode root = new TreeNode(i);
...
}
但是如果按照上述递归函数的方法写，每次递归只能返回一颗树。
多颗树，将不同的根结点装入List然后返回。
public List<TreeNode> helper(int start, int end){
List<TreeNode> list = new ArrayList<>();
if(start > end){
list.add(null);
return list;
}
for(int i = start; i <= end; i++){
TreeNode root = new TreeNode(i);
...
...
// 装入所有根结点
list.add(root);
}
return list;
}
递归构建左子树，并拿到左子树所有可能的根结点列表left
递归构建右子树，并拿到右子树所有可能的根结点列表right
有了左右子树列表，而左右子树都是各不相同的，因为根结点不同，下一步通过左右子树列表构建出所有的以root为根的树。
固定一个左孩子，遍历右子树列表，那么以当前为root根结点的树个数就为left.size() * right.size()个。
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n < 1)
return new ArrayList<>();
return helper(1, n);
}
public List<TreeNode> helper(int start, int end){
List<TreeNode> list = new ArrayList<>();
if(start > end){
// 如果当前子树为空，不加null行吗？
list.add(null);
return list;
}
for(int i = start; i <= end; i++){
// 想想为什么这行不能放在这里，而放在下面？
// TreeNode root = new TreeNode(i);
List<TreeNode> left = helper(start, i-1);
List<TreeNode> right = helper(i+1, end);
// 固定左孩子，遍历右孩子
for(TreeNode l : left){
for(TreeNode r : right){
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
list.add(root);
}
}
}
return list;
}
}
[antione](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/cong-gou-jian-dan-ke-shu-dao-gou-jian-suo-you-shu-/)
如有侵权，私聊删除。
这个只是做个笔记，决定大佬的想法很好做个摘抄。
