package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
	if n == 0 {
		return []*TreeNode{}
	}
	G := make([][]*TreeNode, n+1)
	G[0] = []*TreeNode{nil}
	G[1] = []*TreeNode{&TreeNode{1, nil, nil}}
	for i := 2; i <= n; i++ {
		G[i] = make([]*TreeNode, 0)
		for j := 1; j <= i; j++ {
			// G(i) = sum F(j, i)
			// F(j, i) = G(j-1) * G(i-j)
			for k := 0; k < len(G[j-1]); k++ {
				for l := 0; l < len(G[i-j]); l++ {
					right := copyAndAddBiTree(G[i-j][l], j)
					root := &TreeNode{j, G[j-1][k], right}
					G[i] = append(G[i], root)
				}
			}
		}
	}
	return G[n]
}

func copyAndAddBiTree(src *TreeNode, val int) *TreeNode {
	if src == nil {
		return nil
	}
	dst := TreeNode{src.Val + val, nil, nil}
	dst.Left = copyAndAddBiTree(src.Left, val)
	dst.Right = copyAndAddBiTree(src.Right, val)
	return &dst
}

// func main() {
// 	for _, root := range generateTrees(3) {
// 		printTree(root)
// 		println()
// 	}
// }