leetcode

commit 2231d61cbb2d0e5894bbb3ee04c8cb1194453a3b
parent ec6d4815de18f268837c49c4804d9964b2b005cb
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 23 Jul 2023 20:02:17 +0200

Daily Problem

Diffstat:
A
Problems/0894.cpp
 | 
35
+++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/0894.cpp b/Problems/0894.cpp
@@ -0,0 +1,35 @@
+class Solution {
+  TreeNode *duplicate(TreeNode *root) {
+    TreeNode *dup = new TreeNode(root->val);
+    if (root->left) dup->left = duplicate(root->left);
+    if (root->right) dup->right = duplicate(root->right);
+    return dup;
+  }
+
+  vector<TreeNode *> dp[20];
+
+public:
+  vector<TreeNode *> allPossibleFBT(int n) {
+    if (n % 2 == 0) return {};
+    if (1 == n) return {new TreeNode(0)};
+
+    if (!dp[n].empty()) return dp[n];
+
+    vector<TreeNode *> ret;
+    for (int i = 2; i <= n; i += 2) {
+      auto left = allPossibleFBT(i - 1);
+      auto right = allPossibleFBT(n - i);
+      for (int l = 0; l < left.size(); l++) {
+        for (int r = 0; r < right.size(); r++) {
+          ret.push_back(new TreeNode(0));
+          ret.back()->left =
+              (r == right.size() - 1) ? left[l] : duplicate(left[l]);
+          ret.back()->right =
+              (l == left.size() - 1) ? right[r] : duplicate(right[r]);
+        }
+      }
+    }
+
+    return dp[n] = ret;
+  }
+};
diff --git a/README.md b/README.md
@@ -376,6 +376,7 @@ for solving problems.
 |  0881  |   Medium   | [Boats to Save People](Problems/0881.cpp)                                                        |
 |  0884  |    Easy    | [Uncommon Words from Two Sentences](Problems/0884.cpp)                                           |
 |  0886  |   Medium   | [Possible Bipartition](Problems/0886.cpp)                                                        |
+|  0894  |   Medium   | [All Possible Full Binary Trees](Problems/0894.cpp)                                              |
 |  0897  |    Easy    | [Increasing Order Search Tree](Problems/0897.cpp)                                                |
 |  0901  |   Medium   | [Online Stock Span](Problems/0901.cpp)                                                           |
 |  0904  |   Medium   | [Fruit Into Baskets](Problems/0904.cpp)                                                          |