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)


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 }
8 vector<TreeNode *> dp[20];
10 public:
11 vector<TreeNode *> allPossibleFBT(int n) {
12 if (n % 2 == 0) return {};
13 if (1 == n) return {new TreeNode(0)};
15 if (!dp[n].empty()) return dp[n];
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 }
30 return dp[n] = ret;
31 }
32 };