95. Unique Binary Search Trees II

给定1到n这n个数，用它们能够构成多少种形状不同的二叉搜索树。将所有的二叉搜索树罗列出来。

Go：

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
// 7 star, 多次未能解决，因此给七星，重点关注
func generateTrees(n int) []*TreeNode {
	if n == 0 {return []*TreeNode{}}
	ret := dfs(1, n)
	return ret

}

func dfs(start, end int) []*TreeNode {
	if start > end {return []*TreeNode{nil}}
	ret := []*TreeNode{}
	for mid:=start; mid<end+1; mid++ {
		left := dfs(start, mid-1)
		right := dfs(mid+1, end)

		for _, l := range left {
			for _, r := range right {
				root := TreeNode{mid, nil, nil}
				root.Left, root.Right = l, r
				ret = append(ret, &root)
			}
		}

	}
	return ret
}