894. All Possible Full Binary Trees

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:
![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/22/fivetrees.png)

Note:

• 1 <= N <= 20

# @lc code=start
using LeetCode

function all_possible_fbt(N::Int)
    cache_res = [TreeNode{Int}[] for i in 1:N]
    cache_res[1] = [TreeNode(0)]
    if N % 2 == 0
        return TreeNode{Int}[]
    end
    for n in 3:2:N
        for i in 1:2:n-1
            lres = cache_res[i]
            rres = cache_res[n-i-1]
            append!(cache_res[n], TreeNode(0, lr, rr) for lr in lres for rr in rres)
        end
    end
    return cache_res[N]
end
# @lc code=end

all_possible_fbt (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.