/**
* 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 {
res := []*TreeNode{}
if l > r {
res = append(res, nil)
return res
}
for i := l; i <= r; i++ {
left := dfs(l, i-1)
right := dfs(i+1, r)
for _, lnode := range left {
for _, rnode := range right {
root := &TreeNode{Left: lnode, Right: rnode, Val: i}
res = append(res, root)
}
}
}
return res
}
return dfs(1, n)
}