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:
Runtime: 104 ms, faster than 53.23% of C++ online submissions for All Possible Full Binary Trees.
用map来优化。
class Solution {
private:
unordered_map<int,vector<TreeNode*>> mp;
public:
vector<TreeNode*> allPossibleFBT(int N) {
vector<TreeNode*> ret, leftvec, rightvec;
if(N & 1 == 0 || N <= 0) return ret;
return helper(N);
}
vector<TreeNode*> helper(int N){
vector<TreeNode*> leftvec, rightvec, ret;
if(mp.count(N)) return mp[N];
if(N == 1) return {new TreeNode(0)};
for(int i=1; i < N; i+=2){
leftvec = helper(i);
rightvec = helper(N - i -1);
//cout << leftvec.size() << rightvec.size() << endl;
for(int l = 0; l<leftvec.size();l++){
for(int r = 0; r<rightvec.size();r++){
TreeNode* tmp = new TreeNode(0);
tmp->left = leftvec[l];
tmp->right = rightvec[r];
ret.push_back(tmp);
}
}
}
//cout << ret.size() << endl;
mp[N] = ret;
return ret;
}
};