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.