> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/cartesian-product/all-possible-full-binary-trees.md).

# All Possible Full Binary Trees

<https://leetcode.com/problems/all-possible-full-binary-trees/description/>

> 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.

## Thougts

看到这种所有可能的树的问题应该想到把树分成左右两只。两只的各种可能情况的组合就是答案。让FBT(N) be the list of all possible full binary trees with N nodes，因为是full tree, N只能是奇数，设FBT(x)为左子树有x个节点时的所有可能情况，那么右子树所有可能情况即FBT(N - x -1). 再两个循环把左子树情况和右子树情况做个笛卡尔积就可以了。

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, List<TreeNode>> cache = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int N) {
        if (cache.containsKey(N)) {
            return cache.get(N);
        }
        List<TreeNode> res = new ArrayList<>();
        if (N == 1) {
            res.add(new TreeNode(0));
        } else if ((N & 1) == 1) {
            for (int x = 1; x < N; x++) {
                int y = N - x - 1;
                for (TreeNode left : allPossibleFBT(x)) {
                    for (TreeNode right : allPossibleFBT(y)) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        res.add(root);
                    }
                }
            }
        }

        return res;
    }
}
```

## Analysis

<https://leetcode.com/problems/all-possible-full-binary-trees/solution/>

总数目是个卡特兰数，O(2^N).