# 894. All Possible Full Binary Trees

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`

{% hint style="info" %}
基本的Recursion的方法。
{% endhint %}

```cpp
vector<TreeNode*> allPossibleFBT(int N) {
    vector<TreeNode*> res;
    if (N == 1) {
        res.push_back(new TreeNode(0));
        return res;
    }
    N -= 1;
    for (int i = 1; i < N; i += 2) {
        vector<TreeNode*> lefts = allPossibleFBT(i);
        vector<TreeNode*> rights = allPossibleFBT(N - i);
        for (TreeNode* l : lefts) {
            for (TreeNode* r : rights) {
                TreeNode* cur = new TreeNode(0);
                cur->left = l;
                cur->right = r;
                res.push_back(cur);
            }
        }
    }
    return res;
}
```

{% hint style="info" %}
第一個方法會有許多重複計算的部分，所以想要利用unordered\_map去紀錄以省去重複操作的時間。
{% endhint %}

```cpp
vector<TreeNode*> helper(int N, unordered_map<int, vector<TreeNode*> >& mp) {
    if (mp.count(N)) return mp[N];
    vector<TreeNode*> res;
    if (N == 1) {
        res.push_back(new TreeNode(0));
        return res;
    }
    if (N & 1) {
        N -= 1;
        for (int i = 1; i < N; i += 2) {
            vector<TreeNode*> lefts = helper(i, mp);
            vector<TreeNode*> rights = helper(N - i, mp);
            for (TreeNode* l : lefts) {
                for (TreeNode* r : rights) {
                    TreeNode* cur = new TreeNode(0);
                    cur->left = l;
                    cur->right = r;
                    res.push_back(cur);
                }
            }
        }
        mp[N] = res;
    }
    return res;
}
vector<TreeNode*> allPossibleFBT(int N) {
    unordered_map<int, vector<TreeNode*> > mp;
    return helper(N, mp);
}
```

{% hint style="info" %}
除了top-down recursion也可以用bottom-up dynamic programming。
{% endhint %}

```cpp
// Dynamic Programming Solution
vector<TreeNode*> allPossibleFBT(int N) {
    vector<vector<TreeNode*> > dp(N + 1);
    dp[1].push_back(new TreeNode(0));
    for (int num = 1; num <= N; num += 2) {
        for (int l_num = 1; l_num < num; l_num += 2) {
            for (TreeNode* left : dp[l_num]) {
                for (TreeNode* right : dp[num - 1 - l_num]) {
                    TreeNode* root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    dp[num].push_back(root);
                }
            }
        }
    }
    return dp[N];
}
```

{% hint style="info" %}
但前述三種方法都會有一個實際上操作的問題，每個node都被不同的子數所指到，也就是許多樹之間彼此的節點都互相指來指去，這樣會很混亂，所以理想上應該要重新進行deep copy而不是shallow copy。如果左子數或右子樹已經traverse到最後一個element，那麼就不需要重新deep copy一個新的，因為之後不會有人在用到了。
{% endhint %}

```cpp
TreeNode* clone(TreeNode* root) {
    TreeNode* res = new TreeNode(0);
    res->left = root->left ? clone(root->left) : nullptr;
    res->right = root->right ? clone(root->right) : nullptr;
    return res;
}
vector<TreeNode*> helper(int N, unordered_map<int, vector<TreeNode*> >& mp) {
    if (mp.count(N)) return mp[N];
    vector<TreeNode*> res;
    if (N == 1) {
        res.push_back(new TreeNode(0));
        return res;
    }
    if (N & 1) {
        N -= 1;
        for (int i = 1; i < N; i += 2) {
            vector<TreeNode*> lefts = helper(i, mp);
            vector<TreeNode*> rights = helper(N - i, mp);
            for (int l = 0; l < lefts.size(); ++l) {
                for (int r = 0; r < rights.size(); ++r) {
                    TreeNode* cur = new TreeNode(0);
                    cur->left = (l == lefts.size() - 1) ? lefts[l] : clone(lefts[l]);
                    cur->right = (r == rights.size() - 1) ? rights[r] : clone(rights[r]);
                    res.push_back(cur);
                }
            }
        }
        mp[N] = res;
    }
    return res;
}
vector<TreeNode*> allPossibleFBT(int N) {
    unordered_map<int, vector<TreeNode*> > mp;
    return helper(N, mp);
}
```
