leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0894.cpp (1072B)

0 class Solution { 1 TreeNode *duplicate(TreeNode *root) { 2 TreeNode *dup = new TreeNode(root->val); 3 if (root->left) dup->left = duplicate(root->left); 4 if (root->right) dup->right = duplicate(root->right); 5 return dup; 6 } 7 8 vector<TreeNode *> dp[20]; 9 10 public: 11 vector<TreeNode *> allPossibleFBT(int n) { 12 if (n % 2 == 0) return {}; 13 if (1 == n) return {new TreeNode(0)}; 14 15 if (!dp[n].empty()) return dp[n]; 16 17 vector<TreeNode *> ret; 18 for (int i = 2; i <= n; i += 2) { 19 auto left = allPossibleFBT(i - 1); 20 auto right = allPossibleFBT(n - i); 21 for (int l = 0; l < left.size(); l++) { 22 for (int r = 0; r < right.size(); r++) { 23 ret.push_back(new TreeNode(0)); 24 ret.back()->left = (r == right.size() - 1) ? left[l] : duplicate(left[l]); 25 ret.back()->right = (l == left.size() - 1) ? right[r] : duplicate(right[r]); 26 } 27 } 28 } 29 30 return dp[n] = ret; 31 } 32 };