95_unique_binary_search_trees_ii

95. 不同的二叉搜索树 II

给你一个整数 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]]

示例 2：

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

提示：

• 1 <= n <= 8

代码参考：

package main

func main() {
    // fmt.Println(generateTrees(3))
}

func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return nil
    }
    return generate(1, n)
}

func generate(start, end int) []*TreeNode {
    var roots []*TreeNode

    switch {
    case start > end: // 某一边子树无节点，左斜树或右斜树
        roots = append(roots, nil)

    case start == end: // 某一边子树只有一个节点
        roots = append(roots, &TreeNode{Val: start})

    case start < end:
        for rootV := start; rootV <= end; rootV++ { // 以 rootV 为根节点
            leftTrees := generate(start, rootV-1)
            rightTrees := generate(rootV+1, end)

            // 组合左右子树
            for _, ltree := range leftTrees {
                for _, rtree := range rightTrees {
                    root := &TreeNode{ // 以 rootV 为根节点的一棵 BST
                        Val:   rootV,
                        Left:  ltree,
                        Right: rtree,
                    }
                    roots = append(roots, root)
                }
            }
        }
    }

    return roots
}