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

解法一：递归

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    var dfs func(l, r int) []*TreeNode
    dfs = func(l, r int) []*TreeNode {
        if l > r {
            return []*TreeNode{nil}
        }
        var ret []*TreeNode
        for i := l; i <= r; i++ {
            left, right := dfs(l, i-1), dfs(i+1, r)
            for j := 0; j < len(left); j++ {
                for k := 0; k < len(right); k++ {
                    ret = append(ret, &TreeNode{Val: i, Left: left[j], Right: right[k]})
                }
            }
        }
        return ret
    }
    return dfs(1, n)
}