leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0894.cpp (1072B)

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