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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/cartesian-product/all-possible-full-binary-trees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.