diff options
Diffstat (limited to 'all_possible_full_tree.cpp')
-rw-r--r-- | all_possible_full_tree.cpp | 40 |
1 files changed, 0 insertions, 40 deletions
diff --git a/all_possible_full_tree.cpp b/all_possible_full_tree.cpp deleted file mode 100644 index ca54570..0000000 --- a/all_possible_full_tree.cpp +++ /dev/null @@ -1,40 +0,0 @@ -// 894. All Possible Full Binary Trees -#include "leetcode.h" - -/* - * 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 zero or two children - */ - -class Solution { -public: - vector<TreeNode *> allPossibleFBT(int n) { - unordered_map<int, vector<TreeNode *>> memo; - vector<TreeNode *> ans; - if (n < 1 || !n % 2) - return ans; - if (memo.find(n) != memo.end()) - return memo[n]; - if (n == 1) { - ans.push_back(new TreeNode(0)); - memo[1] = ans; - return ans; - } - for (int i = 1; i < n; i += 2) { - vector<TreeNode *> left = allPossibleFBT(i); - vector<TreeNode *> right = allPossibleFBT(n - 1 - i); - for (int j = 0; j < left.size(); j++) - for (int k = 0; k < right.size(); k++) { - TreeNode *root = new TreeNode(0); - root->left = left[j]; - root->right = right[k]; - ans.push_back(root); - } - } - memo[n] = ans; - return ans; - } -}; |