LeetCode-100题(Hot) 95. 不同的二叉搜索树 II [Java实现] [极速]

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

示例 1：

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

对于一棵二叉搜索树，我们如此构建：

    private TreeNode generateTree(int start, int end) {
        if (start > end) {
            return null;
        }
        int root = (start+end) / 2;
        TreeNode left = generateTree(start, root-1);
        TreeNode right = generateTree(root+1, end);
        return new TreeNode(root, left, right);
    }

则对于所有可能的二叉树，我们可以依次枚举所有可能的根节点并递归得到其左右节点，对于每次递归得到的所有左右节点，我们用List储存起来进行枚举。实现如下：

    public List generateTrees(int n) {
        return generateTrees(1, n);
    }

    private List generateTrees(int start, int end) {
        List nodes = new ArrayList<>();
        if (start >= end) {
            nodes.add(start == end ? new TreeNode(start) : null);
            return nodes;
        }
        for (int root = start; root <= end; ++ root) {
            for (TreeNode left : generateTrees(start, root-1)) {
                for (TreeNode right : generateTrees(root+1, end)) {
                    nodes.add(new TreeNode(root, left, right));
                }
            }
        }
        return nodes;
    }