leetcode 894

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

示例：

image

提示：

• 1 <= N <= 20

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */


func allPossibleFBT(N int) []*TreeNode {
    var set = map[int][]*TreeNode{0:[]*TreeNode{&TreeNode{Val: 0}}}
  
    var helper func(N int)[]*TreeNode
    helper = func(N int)[]*TreeNode{
        if N & 1 == 0{
            return nil
        }
        res := []*TreeNode{}
        if _,ok := set[N/2]; ok{
            return set[N/2]
        }
        
        for i:=1;i < N-1; i+=2{
            left := helper(i)
            right := helper(N-i-1)
            for _,l :=range left{
                for _,r := range right{
                    node := &TreeNode{
                        Val:0,
                        Left: l,
                        Right:r,
                    }
                    res = append(res,node)
                }
            }
        }
        set[N/2] = res
        return res
    }

    return helper(N)
}