# 894.All Possible Full Binary Trees

**894.All Possible Full Binary Trees**

难度:Medium

> 满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

示例：

输入：7 输出：\[\[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]] 解释：

![fivetrees.png](https://i.loli.net/2019/10/10/GHIbxJ4Vk7FzQ85.png)

提示： 1 <= N <= 20

每个满二叉树的左右子树必须是满二叉树，所以对于一个满二叉树来说，N的所有满二叉树可以有x的满二叉树和(N-X)的满二叉树作为左右子树构成。N必须是奇数。\
可以创建一个数组保存已有的满二叉树，不需要递归。

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
vector<vector<TreeNode*>>allPath;
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        vector<TreeNode*> res;
        if(N%2==0) return res;
        TreeNode* zero = new TreeNode(0);
        res.push_back(zero);
        allPath.push_back(res);

        if(N/2+1 <= allPath.size()) return allPath[N/2];
        int len=allPath.size();
        for(int i=len;i<N/2+1;i++)
        {
            vector<TreeNode*>tmp;
            // cout<<count<<endl;
            for(int j=0;j<i;j++)
            {
                for(auto l : allPath[j])
                for(auto r: allPath[i-1-j])
                {
                TreeNode* root = new TreeNode(0);
                root->left = l;
                root->right = r;
                tmp.push_back(root);
                }
            }
            allPath.push_back(tmp);
        }

        //cout<<res.size()<<endl;

        return allPath[N/2];
    }
};
```

> 执行用时 :132 ms, 在所有 C++ 提交中击败了96.42%的用户\
> 内存消耗 :20.8 MB, 在所有 C++ 提交中击败了90.36%的用户


---

# 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://dfine.gitbook.io/leetcode/894.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.