# LeetCode 894. All Possible Full Binary Trees
[894. All Possible Full Binary Trees](https://leetcode.com/problems/all-possible-full-binary-trees/) (<font color=#FFB800>Medium</font> 82.7%)

<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

<ul>
<li><code>1 <= n <= 20</code></li>
</ul>

- Solution 1
這一題當初在看的時候，覺得難的地方在於，他的結構我完全看不懂要幹嘛。
但是，他其實要求的是: 在數字 n 底下，我要回傳所有可能的 Full Binary Tree 。
1. 當等於1 的時候，我要回傳一個有1個0的 TreeNode。
2. 在等於3 的時候，要回傳一個有3個(root, left_subling, right_subling) 的TreeNode。
3. 以此類推，但超過三的時候，要考慮左右子樹都要放東西，所以會有很多種選擇。

所以在解題的時候，必須考慮所有選項，在程式碼中，會依照每一個子樹考慮進去。
- 時間複雜度: $O(2^n)$
- 空間複雜度: $O(2^n)$

- 程式碼

    class Solution {
    public:
        vector<TreeNode*> allPossibleFBT(int n) {
            if (n % 2 == 0)
                return {};

            if (n == 1)
                return {new TreeNode(0)};

            vector<TreeNode*> results;
            for (int i = 1; i < n; i += 2) {
                for (const auto& l : allPossibleFBT(i)) {
                    for (const auto& r : allPossibleFBT(n - i - 1))
                    {
                        TreeNode* root;
                        root = new TreeNode(0);
                        root->right = r;
                        root->left = l;
                        results.push_back(root);
                    }
                }
            }
            return results;
        }
    };

- Solution 2
但上面的方法會有很多多餘的計算，這時候就要使用 DP 大法，讓速度可以快一點。

- 程式碼

    class Solution {
    public:
        vector<TreeNode*> allPossibleFBT(int n) {
            if (n % 2 == 0)
                return {};

            vector<vector<TreeNode*>> DP_record(n + 1);
            DP_record[1] = {new TreeNode(0)};

            for (int i = 3; i <= n; i += 2) {
                for (int j = 1; j < i; j += 2) {
                    int k = i - j - 1;
                    for (const auto& l: DP_record[j]) {
                        for (const auto& r: DP_record[k]) {
                            TreeNode* root;
                            root = new TreeNode(0);
                            root -> left = l;
                            root -> right = r;
                            DP_record[i].push_back(root);
                        }
                    }
                }
            }
            return DP_record[n];
        }
    };

reference:
1. [花花酱 LeetCode 894. All Possible Full Binary Trees](https://zxi.mytechroad.com/blog/tree/leetcode-894-all-possible-full-binary-trees/)