[894. All Possible Full Binary Trees](https://leetcode.com/problems/all-possible-full-binary-trees/)

### 題目描述

Given an integer `n`, return *a list of all possible **full binary trees** with* `n` *nodes*. Each node of each tree in the answer must have `Node.val == 0`.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in **any order**.

A **full binary tree** is a binary tree where each node has exactly `0` or `2` children.

### 範例

**Example 1:**


Input: n = 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]]

**Example 2:**

Input: n = 3
Output: [[0,0,0]]

**Constraints**:

* 1 <= `n` <= 20

### 解答
#### Python

class Solution:
    @cache
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n == 1:
            return [TreeNode()]
        ans = []
        for i in range(1, n-1, 2):
            ls = self.allPossibleFBT(i)
            rs = self.allPossibleFBT(n - i - 1)
            for l in ls:
                for r in rs:
                    ans.append(TreeNode(0, l, r))
        return ans

> [name=Yen-Chi Chen][time=Sun, Jul 23, 2023]

#### C++

class Solution {
public:
    vector<TreeNode*> cache[20 + 1];

    vector<TreeNode*> allPossibleFBT(int n) {
        vector<TreeNode*> ans;
        if (n == 1) {
            ans.push_back(new TreeNode(0));
        }
        if (cache[n].size() != 0) {
            return cache[n];
        }
        for (int i = 0; i < n; i ++) {
            for (TreeNode* left : allPossibleFBT(i)) {
                for (TreeNode* right : allPossibleFBT(n - i - 1)) {
                    ans.push_back(new TreeNode(0, left, right));
                }
            }
        }
        cache[n] = ans;

        return ans;
    }
};

> [name=Jerry Wu][time=23 July, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)