# 894. All Possible Full Binary Trees 所有可能的真二叉树

@TOC

## # 题目描述

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.

Example 1:

``````Input: 7
Output: [[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]]
Explanation:
``````

Note:

• 1 <= N <= 20

## # 解题方法

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def allPossibleFBT(self, N):
"""
:type N: int
:rtype: List[TreeNode]
"""
N -= 1
if N == 0: return [TreeNode(0)]
res = []
for l in range(1, N, 2):
for left in self.allPossibleFBT(l):
for right in self.allPossibleFBT(N - l):
node = TreeNode(0)
node.left = left
node.right = right
res.append(node)
return res
``````

C++版本的代码如下：

``````/**
* 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 {
public:
vector<TreeNode*> allPossibleFBT(int N) {
N--;
vector<TreeNode*> res;
if (N == 0) {
res.push_back(new TreeNode(0));
return res;
}
for (int i = 1; i < N; i += 2) {
for (auto& left : allPossibleFBT(i)) {
for (auto& right : allPossibleFBT(N - i)) {
TreeNode* root = new TreeNode(0);
root->left = left;
root->right = right;
res.push_back(root);
}
}
}
return res;
}
};
``````

## # 日期

2018 年 8 月 26 日 —— 珍爱生命，远离DD！ 2018 年 12 月 2 日 —— 又到了周日