894. All Possible Full Binary Trees

Problem Description

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

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

Examples:

Input: n = 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]]

Input: n = 3
Output: [[0,0,0]]

Constraints:

• 1 ≤ n ≤ 20
• n is odd

Python Solution

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]]:
        # Memoization dictionary
        memo = {}
        
        def backtrack(n):
            # Base cases
            if n % 2 == 0:
                return []
            if n == 1:
                return [TreeNode(0)]
            if n in memo:
                return memo[n]
            
            res = []
            # Try all possible combinations of left and right subtrees
            for left in range(1, n, 2):
                right = n - 1 - left
                # Get all possible left and right subtrees
                leftTrees = backtrack(left)
                rightTrees = backtrack(right)
                
                # Create all possible combinations
                for l in leftTrees:
                    for r in rightTrees:
                        root = TreeNode(0)
                        root.left = l
                        root.right = r
                        res.append(root)
            
            memo[n] = res
            return res
        
        return backtrack(n)

Implementation Notes:

• Uses dynamic programming with memoization
• Time complexity: O(2^n)
• Space complexity: O(2^n)

Java Solution

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 {
    Map> memo = new HashMap<>();
    
    public List allPossibleFBT(int n) {
        if (n % 2 == 0) return new ArrayList<>();
        if (n == 1) return Arrays.asList(new TreeNode(0));
        if (memo.containsKey(n)) return memo.get(n);
        
        List res = new ArrayList<>();
        for (int left = 1; left < n; left += 2) {
            int right = n - 1 - left;
            for (TreeNode l : allPossibleFBT(left)) {
                for (TreeNode r : allPossibleFBT(right)) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        
        memo.put(n, res);
        return res;
    }
}

C++ Solution

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
    unordered_map> memo;
public:
    vector allPossibleFBT(int n) {
        if (n % 2 == 0) return {};
        if (n == 1) return {new TreeNode(0)};
        if (memo.count(n)) return memo[n];
        
        vector res;
        for (int left = 1; left < n; left += 2) {
            int right = n - 1 - left;
            for (TreeNode* l : allPossibleFBT(left)) {
                for (TreeNode* r : allPossibleFBT(right)) {
                    TreeNode* root = new TreeNode(0);
                    root->left = l;
                    root->right = r;
                    res.push_back(root);
                }
            }
        }
        
        return memo[n] = res;
    }
};

JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var allPossibleFBT = function(n) {
    const memo = new Map();
    
    const backtrack = (n) => {
        if (n % 2 === 0) return [];
        if (n === 1) return [new TreeNode(0)];
        if (memo.has(n)) return memo.get(n);
        
        const res = [];
        for (let left = 1; left < n; left += 2) {
            const right = n - 1 - left;
            const leftTrees = backtrack(left);
            const rightTrees = backtrack(right);
            
            for (const l of leftTrees) {
                for (const r of rightTrees) {
                    const root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    res.push(root);
                }
            }
        }
        
        memo.set(n, res);
        return res;
    };
    
    return backtrack(n);
};

C# Solution

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private Dictionary> memo = new Dictionary>();
    
    public IList AllPossibleFBT(int n) {
        if (n % 2 == 0) return new List();
        if (n == 1) return new List { new TreeNode(0) };
        if (memo.ContainsKey(n)) return memo[n];
        
        var res = new List();
        for (int left = 1; left < n; left += 2) {
            int right = n - 1 - left;
            foreach (var l in AllPossibleFBT(left)) {
                foreach (var r in AllPossibleFBT(right)) {
                    var root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    res.Add(root);
                }
            }
        }
        
        memo[n] = res;
        return res;
    }
}

Implementation Notes:

• Uses dictionary for memoization
• Recursive approach with dynamic programming
• Handles even numbers efficiently