https://leetcode.cn/problems/unique-binary-search-trees-ii/
class Solution {// 宫水三叶姐解释的很好,可以参考她的解释,我的注释可能没那么明确
// 根据二叉搜索搜索的特性，若某个子树的根节点为 root，那么 root 的左子树任意节点值均比 root.val 要小，root 的右子树任意节点值均比 root.val 要大。
//
// 因此，假设我们使用 [l,r] 连续段来构造二叉搜索树，并且选择了节点 t 作为二叉搜索树的根节点时，那么使用 [l,t−1] 构造出来的二叉搜索树均可作为根节点 t 的左子树；同理，使用 [t+1,r] 构造出来的二叉搜索树均可作为根节点 t 的右子树。
//
// 也就是说，我们可以设计递归函数 List<TreeNode> dfs(int l, int r)，含义为使用连续段 [l,r] 进行二叉搜索树构造，并返回相应集合。
//
// 最终答案为 dfs(1, n)，起始我们可以枚举 [1,n] 范围内的的每个数 t 作为根节点，并递归 dfs(l, t - 1) 和 dfs(t + 1, r) 获取左右子树的集合 left 和 right，结合「乘法原理」，枚举任意左子树和任意右子树，即可得到 t 作为根节点的二叉搜索树方案集，枚举所有 t 后即可得到所有二叉搜索树的总集。
//
// 注意：当我们运用乘法原理，来构造以 t 为根节点的二叉搜索树时，其 left 或 right 某一边可能为空集，但此时我们仍要将非空的一边子树进行挂载。
// 为了确保两层新循环的逻辑会被执行，对于空集我们不能使用 null 来代指，而要使用 [null] 来代指。public List<TreeNode> generateTrees(int n) {return dfs(1, n);}// dfs(start,end)表示使用区间[start,end]作为根节点去构建二叉搜索树,所能得到的所有可能的二叉搜索树// 这样使用区间传参可以很好的区分左右子树的节点值域,这是根据二叉搜索树的特性推导得到的private List<TreeNode> dfs(int start, int end) {List<TreeNode> res = new ArrayList<>();if (start > end) {// 填充null,而不是返回emptyList或者null,否则下面的合并循环无法执行res.add(null);return res;}for (int i = start; i <= end; i++) {List<TreeNode> l = dfs(start, i - 1);List<TreeNode> r = dfs(i + 1, end);// 合并左右子树,左右子树的所有可能方案之间的关系是乘法原理for (TreeNode left : l) {for (TreeNode right : r) {TreeNode root = new TreeNode(i);root.left = left;root.right = right;res.add(root);}}}return res;}
}