给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
题解
可以先做Leetcode 96再做本题：
两题有着相似的思想，都是遍历数组[1,n]，通过当前节点i将数组划分为左子树集合[1,i-1]，根节点i和右子树集合[i+1,end]
不同的是96题只需要返回满足条件的二叉搜索树的数目，而本题需要构造二叉搜索树并返回，那么先从构造一颗二叉搜索树开始：
1. 构建一颗二叉搜索树（只需要选择一个根结点，然后递归去构建其左右子树。）
以下转载自Krains
构建一颗二叉搜索树很简单，只需要选择一个根结点，然后递归去构建其左右子树。
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;
}2.构造多棵二叉树（遍历所有根节点递归构造左右子树，并将构造后的根节点装入结果集返回）
要构建多颗二叉树，问题就在于如何选择不同的根节点，以构建不同的树和子树。
在上面的代码中，在选择根结点的时候，可以这样改造
// 选择所有可能的根结点
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);......// 装入以所有根结点[1,n]list.add(root);}return list;}
很显然，现在问题变成了如何构建root的左右子树，我们抛开复杂的递归函数，只关心递归的返回值，每次选择根结点root，我们
- 递归构建左子树，并拿到左子树所有可能的根结点列表left
- 递归构建右子树，并拿到右子树所有可能的根结点列表right
这个时候我们有了左右子树列表，我们的左右子树都是各不相同的，因为根结点不同。通过遍历左子树并选定一个左孩子，遍历右子树列表选中一个右孩子，将左右子树分别拼接到当前根节点上，这样可以构建出所有的以root为根的树
算法实现
定义 dfs(start, end) ：返回序列 [start,end] 生成的所有可行的二叉搜索树。
枚举 [start,end] 中的值 i 为当前二叉搜索树的根，那么序列划分为了 [start,i−1] 和 [i+1,end] 两部分。递归调用这两部分，即 dfs(start, i - 1) 和 dfs(i + 1, end),递归的入口即为 dfs(1, n).
- 递归终止：当 start>end 的时候，当前二叉搜索树为空，返回空节点即可。
枚举[start,end]中可行根节点i： - 向下递归：递归获得所有可行的左子树（dfs(start,i-1)）和可行的右子树(dfs(i+1,end))
- 本层操作：对于当前根节点i，从可行左子树集合中选一棵（选中头结点即可），再从可行右子树集合中选一棵,拼接到根节点(new TreeNode(i))，并将生成的二叉搜索树放入答案数组即可。
class Solution {//List是包含所有搜索树的根节点的集合public List<TreeNode> generateTrees(int n) {return dfs(1,n);}public List<TreeNode> dfs(int start,int end){//将不同的根结点装入List然后返回List<TreeNode> list = new LinkedList<TreeNode>();//递归终止：if (start > end) {list.add(null);return list;}// 枚举可行根节点for (int i = start; i <= end; i++) {//此处返回的是不同的左子树集合List<TreeNode> leftTrees=dfs(start,i-1);//此处返回的是不同的右子树集合List<TreeNode> rightTrees=dfs(i+1,end);//从左右子树集合中选一颗拼接到当前根节点i上for(TreeNode left:leftTrees){for(TreeNode right:rightTrees){TreeNode root = new TreeNode(i);root.left=left;root.right=right;//将以i为根节点的树加入结果集list.add(root);}}}//如果按照构造单棵树的逻辑此处返回root，每次递归只能返回一颗树，我们需要的是多颗树，所以此处需要返回list集合return list;}
}
