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

基本的Recursion的方法。

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;
}

第一個方法會有許多重複計算的部分，所以想要利用unordered_map去紀錄以省去重複操作的時間。

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);
}

除了top-down recursion也可以用bottom-up dynamic programming。

// 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];
}

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

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);
}