##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/894.html

# 894. All Possible Full Binary Trees (Medium)

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

Companies:

Related Topics:
Tree, Recursion

## Solution 1.

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> allPossibleFBT(int N) {
if (N % 2 == 0)
return new ArrayList<TreeNode>();
Map<Integer, List<TreeNode>> map = new HashMap<Integer, List<TreeNode>>();
List<TreeNode> oneList = new ArrayList<TreeNode>();
map.put(1, oneList);
for (int i = 3; i <= N; i += 2) {
List<TreeNode> curList = map.getOrDefault(i, new ArrayList<TreeNode>());
int sum = i - 1;
for (int left = 1; left < sum; left++) {
int right = sum - left;
List<TreeNode> leftList = map.getOrDefault(left, new ArrayList<TreeNode>());
List<TreeNode> rightList = map.getOrDefault(right, new ArrayList<TreeNode>());
for (TreeNode leftNode : leftList) {
for (TreeNode rightNode : rightList) {
TreeNode root = new TreeNode(0);
root.left = leftNode;
root.right = rightNode;
}
}
}
map.put(i, curList);
}
return map.get(N);
}
}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
private List<TreeNode>[] f = new List[21];

public List<TreeNode> allPossibleFBT(int n) {
return dfs(n);
}

private List<TreeNode> dfs(int n) {
if (f[n] != null) {
return f[n];
}
if (n == 1) {
return Collections.singletonList(new TreeNode());
}
List<TreeNode> res = new ArrayList<>();
for (int i = 0; i < n - 1; ++i) {
int j = n - i - 1;
for (TreeNode left : dfs(i)) {
for (TreeNode right : dfs(j)) {
}
}
}
f[n] = res;
return res;
}
}

• // OJ: https://leetcode.com/problems/all-possible-full-binary-trees/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
vector<TreeNode*> allPossibleFBT(int N) {
if (N % 2 == 0) return {};
if (N == 1) return { new TreeNode(0) };
vector<TreeNode*> ans;
for (int i = 1; i <= N - 2; i += 2) {
auto lefts = allPossibleFBT(i);
auto rights = allPossibleFBT(N - i - 1);
for (auto left : lefts) {
for (auto right : rights) {
auto root = new TreeNode(0);
root->left = left;
root->right = right;
ans.push_back(root);
}
}
}
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
@cache
def dfs(n):
if n == 1:
return [TreeNode()]
res = []
if n % 2:
for i in range(n - 1):
j = n - i - 1
for left in dfs(i):
for right in dfs(j):
res.append(TreeNode(0, left, right))
return res

return dfs(n)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def allPossibleFBT(self, N):
"""
:type N: int
:rtype: List[TreeNode]
"""
N -= 1
if N == 0: return [TreeNode(0)]
res = []
for l in range(1, N, 2):
for left in self.allPossibleFBT(l):
for right in self.allPossibleFBT(N - l):
node = TreeNode(0)
node.left = left
node.right = right
res.append(node)
return res

• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func allPossibleFBT(n int) []*TreeNode {
f := map[int][]*TreeNode{}
var dfs func(n int) []*TreeNode
dfs = func(n int) []*TreeNode {
if v, ok := f[n]; ok {
return v
}
if n == 1 {
return []*TreeNode{&TreeNode{Val: 0} }
}
res := []*TreeNode{}
for i := 0; i < n-1; i++ {
j := n - i - 1
for _, left := range dfs(i) {
for _, right := range dfs(j) {
res = append(res, &TreeNode{0, left, right})
}
}
}
f[n] = res
return res
}
return dfs(n)
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function allPossibleFBT(n: number): Array<TreeNode | null> {
const f: Array<Array<TreeNode | null>> = new Array(n + 1)
.fill(0)
.map(() => []);
const dfs = (n: number): Array<TreeNode | null> => {
if (f[n].length) {
return f[n];
}
if (n === 1) {
f[n].push(new TreeNode(0));
return f[n];
}
const ans: Array<TreeNode | null> = [];
for (let i = 0; i < n - 1; ++i) {
const j = n - 1 - i;
for (const left of dfs(i)) {
for (const right of dfs(j)) {
ans.push(new TreeNode(0, left, right));
}
}
}
return (f[n] = ans);
};
return dfs(n);
}


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }

impl TreeNode {
pub fn new_with_node(left: Option<Rc<RefCell<TreeNode>>>, right: Option<Rc<RefCell<TreeNode>>>) -> Self {
Self {
val: 0,
left,
right,
}
}
}

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
let mut record_vec = vec![vec![]; n as usize + 1];
Self::dfs(n, &mut record_vec)
}

fn dfs(n: i32, record_vec: &mut Vec<Vec<Option<Rc<RefCell<TreeNode>>>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
if record_vec[n as usize].len() != 0 {
return record_vec[n as usize].clone();
}
if n == 1 {
// Just directly return a single node
return vec![Some(Rc::new(RefCell::new(TreeNode::new(0))))];
}
// Otherwise, need to construct return vector
let mut ret_vec = Vec::new();

// Enumerate the node number for left subtree from 0 -> n - 1
for i in 0..n - 1 {
// The number of right subtree node
let j = n - i - 1;
for left in Self::dfs(i, record_vec) {
for right in Self::dfs(j, record_vec) {
// Construct the ret vector
ret_vec.push(Some(Rc::new(RefCell::new(TreeNode::new_with_node(left.clone(), right.clone())))));
}
}
}

record_vec[n as usize] = ret_vec;

record_vec[n as usize].clone()
}
}