LeetCode 894 - All Possible Full Binary Trees

https://leetcode.com/articles/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.

Let $\text{FBT}(N)$ be the list of all possible full binary trees with $N$ nodes.

Every full binary tree $T$ with 3 or more nodes, has 2 children at its root. Each of those children left and right are themselves full binary trees.

Thus, for $N \geq 3$, we can formulate the recursion: $\text{FBT}(N) =$ [All trees with left child from $\text{FBT}(x)$ and right child from $\text{FBT}(N-1-x)$, for all $x$].

Also, by a simple counting argument, there are no full binary trees with a positive, even number of nodes.

Finally, we should cache previous results of the function $\text{FBT}$ so that we don't have to recalculate them in our recursion.

• Time Complexity: $O(2^N)$. For odd $N$, let $N = 2k + 1$. Then, $\Big| \text{FBT}(N) \Big| = C_k$, the $k$-th catalan number; and $\sum\limits_{k < \frac{N}{2}} C_k$ (the complexity involved in computing intermediate results required) is bounded by $O(2^N)$. However, the proof is beyond the scope of this article.
• Space Complexity: $O(2^N)$. 

    Map<Integer, List<TreeNode>> memo = new HashMap();

    public List<TreeNode> allPossibleFBT(int N) {
        if (!memo.containsKey(N)) {
            List<TreeNode> ans = new LinkedList();
            if (N == 1) {
                ans.add(new TreeNode(0));
            } else if (N % 2 == 1) {
                for (int x = 0; x < N; ++x) {
                    int y = N - 1 - x;
                    for (TreeNode left: allPossibleFBT(x))
                        for (TreeNode right: allPossibleFBT(y)) {
                            TreeNode bns = new TreeNode(0);
                            bns.left = left;
                            bns.right = right;
                            ans.add(bns);
                        }
                }
            }
            memo.put(N, ans);
        }

        return memo.get(N);
    }
https://leetcode.com/problems/all-possible-full-binary-trees/discuss/163433/Java-Recursive-Solution-with-Explanation


https://zxi.mytechroad.com/blog/tree/leetcode-894-all-possible-full-binary-trees/

public List<TreeNode> allPossibleFBT(int N) {     List<TreeNode> ans = new ArrayList<>();     if (N % 2 == 0) return ans;     if (N == 1) {       ans.add(new TreeNode(0));       return ans;     }     for (int i = 1; i < N; i += 2) {       for (TreeNode l : allPossibleFBT(i))         for (TreeNode r : allPossibleFBT(N - i - 1)) {           TreeNode root = new TreeNode(0);           root.left = l;           root.right = r;           ans.add(root);         }               }     return ans;   }