894. 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
class Solution { public: vector<TreeNode*> allPossibleFBT(int n) { if(!(n & 1)) return {}; if(n == 1) return {new TreeNode()}; vector<TreeNode*> res; vector<vector<TreeNode*>> childs; for(int l = 1; l < n - 1; l += 2) { vector<TreeNode*> child = allPossibleFBT(l); childs.push_back(child); } for(int i = 0; i < childs.size(); i++) { for(auto& ll : childs[i]) { for(auto& rr : childs[childs.size() - 1 - i]) { res.push_back(new TreeNode(0, ll, rr)); } } } return res; } };
|