leetcode 894. All Possible Full Binary Trees 所有可能的真二叉树-耗时100

Problem: 894. All Possible Full Binary Trees 所有可能的真二叉树

耗时100%

1和3的答案可以手写出来，5是1+（1+3）或者1+（3+1），7是1+（1+5）或者1+（5+1）或者1+（3+3），第一个1是根节点，括号内分别是左节点和右节点，然后（1+5）其中1一种情况5两种情况，所以7共2+2+1=5种情况，9可以写成1+（1+7）、1+（7+1）、1+（2+5）等

所以可以使用记忆化搜索，依次组合起来就可以得到答案，但是需要复制一遍二叉树

Code

class Solution { public: vector<TreeNode*> ret; unordered_map<int, vector<TreeNode*>> ump; TreeNode* copy(TreeNode* root, TreeNode* rt) { if(root==nullptr) return nullptr; if(rt==nullptr) { rt = new TreeNode(0); } rt->left = copy(root->left, rt->left); rt->right = copy(root->right, rt->right); return rt; } // TreeNode* rootroot; // void dfs(TreeNode* root, int n) { // if(n == 0) { // TreeNode* rt = nullptr; // rt = copy(rootroot, rt); // ret.push_back(rt); // delete root->left; // delete root->right; // root->left = nullptr; // root->right = nullptr; // return; // } // root->left = new TreeNode(0); // root->right = new TreeNode(0); // dfs(root->left, n - 2); // dfs(root->right, n - 2); // // delete root->left; // // root->left = nullptr; // // delete root->right; // // root->right = nullptr; // // dfs(root->right, n - 2); // } vector<TreeNode*> allPossibleFBT(int n) { if((n&1)==0) return {}; TreeNode* root; root = new TreeNode(0); if(n==1) { return {root}; }; TreeNode* rt = nullptr; rt = copy(root, rt); ump[1] = {rt}; root->left = new TreeNode(0); root->right = new TreeNode(0); rt = nullptr; rt = copy(root, rt); ump[3] = {rt}; if(n==3) { return ump[3]; } for(int k = 5; k <= n; k += 2) { for(int i = 1; i <= (k-1)/2; i+=2) { for(TreeNode* l : ump[i]) { for(TreeNode* r : ump[k - i - 1]) { if(2*i!=k-1) { root = new TreeNode(0); root->left = l; root->right = r; // rt = nullptr; // rt = copy(root, rt); ump[k].push_back(root); root = new TreeNode(0); root->left = r; root->right = l; // rt = nullptr; // rt = copy(root, rt); ump[k].push_back(root); } else { root = new TreeNode(0); root->left = l; root->right = r; // rt = nullptr; // rt = copy(root, rt); ump[k].push_back(root); } } } } } // dfs(root, n - 1); return ump[n]; } };