# Leetcode: All Possible Full Binary Trees

All Possible Full Binary Trees

Similar Problems:

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

```Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:
```

Note:

• 1 <= N <= 20

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution: Recursive
```// Blog link: https://code.dennyzhang.com/all-possible-full-binary-trees
// Basic Ideas: Recursive
// If n is even, return nil
//
// Complexity: Time O(2^n), Space O(2^n)
/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
var m map[int][]*TreeNode

func allPossibleFBT(N int) []*TreeNode {
if N%2 == 0 { return []*TreeNode{} }
if len(m) == 0 {
m = map[int][]*TreeNode{}
}
v, ok := m[N]
if ok { return v }

if N == 1 {
m[N] = []*TreeNode{&TreeNode{0, nil, nil}}
return m[N]
}

res := []*TreeNode{}
for i:= 1; i < N; i += 2 {
l1, l2 := allPossibleFBT(i), allPossibleFBT(N-1-i)
for _, p := range l1 {
for _, q := range l2 {
res = append(res, &TreeNode{0, p, q})
}
}
}
return res
}
```

Share It, If You Like It.