All Possible Full Binary Trees

This approach directly translates the recursive definition of a full binary tree into a function. A full binary tree with n nodes is formed by a root, a left full binary subtree, and a right full binary subtree. The total number of nodes n must be odd. If n=1, it's a single node. For n > 1, we can partition the remaining n-1 nodes into a left subtree with i nodes and a right subtree with n-1-i nodes. Since both subtrees must also be full binary trees, i and n-1-i must be odd. We can iterate through all possible odd values for i, recursively generate all possible left and right subtrees, and combine them.

• The function allPossibleFBT(n) is defined to return a list of all full binary trees with n nodes.
• Base Case 1: If n is an even number, it's impossible to form a full binary tree. Return an empty list.
• Base Case 2: If n is 1, the only possible tree is a single node. Return a list containing just this node.
• Recursive Step: For an odd n > 1, iterate through all possible odd numbers for the left subtree's node count, let's call it i, from 1 to n-2.
• For each i, the right subtree must have j = n - 1 - i nodes.
• Recursively call allPossibleFBT(i) to get all possible left subtrees.
• Recursively call allPossibleFBT(j) to get all possible right subtrees.
• Create a new tree for every combination of a left subtree and a right subtree. A new root node is created, and its left and right children are set to the pair of subtrees.
• Add each newly formed tree to a result list.
• Return the final list of trees.

The core idea is to break down the problem of finding trees with n nodes into smaller subproblems. We observe the inherent recursive structure: any full binary tree with more than one node has a root, a left subtree, and a right subtree, both of which must also be full binary trees. This leads to a straightforward recursive algorithm.

/**
 * 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 {
    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> result = new ArrayList<>();
        // A full binary tree must have an odd number of nodes.
        if (n % 2 == 0) {
            return result;
        }
        // Base case: a tree with 1 node is just a single node.
        if (n == 1) {
            result.add(new TreeNode(0));
            return result;
        }

        // Iterate through all possible numbers of nodes for the left subtree.
        // The number of nodes in a subtree must also be odd.
        for (int i = 1; i < n; i += 2) {
            int j = n - 1 - i; // Remaining nodes for the right subtree.
            
            List<TreeNode> leftSubtrees = allPossibleFBT(i);
            List<TreeNode> rightSubtrees = allPossibleFBT(j);

            // Combine every possible left subtree with every possible right subtree.
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        return result;
    }
}