95. 不同的二叉搜索树 II(较难)

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

1
2
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

1
2
输入：n = 1
输出：[[1]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii

思路1：

回溯思路，但是没法进行去重，需要再思考思考

思路2：

递归，其实有点难想

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n==0){
            return new ArrayList<TreeNode>();
        }
        return generateTrees(1,n);
    }
    public List<TreeNode> generateTrees(int start,int end){
        List<TreeNode> res = new ArrayList<>();
        //特殊情况
        if(start>end){
            res.add(null);
            return res;
        }
        if(start==end){
            TreeNode root = new TreeNode(start);
            res.add(root);
            return res;
        }
        //一定要等于
        for(int i=start;i<=end;i++){
            List<TreeNode> leftNode = generateTrees(start,i-1);
            List<TreeNode> rightNode = generateTrees(i+1,end);
            //遍历左右子树中的节点
            for(TreeNode left:leftNode){
                for(TreeNode right:rightNode){
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
}