本文主要是介绍894. 所有可能的真二叉树（记忆性搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
直接递归：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<TreeNode*> allPossibleFBT(int n) {if (n % 2 == 0) {return {};}vector<TreeNode*> roots;if(n==1){roots.push_back(new TreeNode(0,nullptr,nullptr));return roots;}for(int left=1;left<=n-1;left+=2){vector<TreeNode*>ltrees= allPossibleFBT(left);vector<TreeNode*>rtrees= allPossibleFBT(n-left-1);for(auto ltree:ltrees){for(auto rtree:rtrees){TreeNode* root = new TreeNode(0,ltree,rtree);roots.push_back(root);}}}return roots;}
};记忆性搜索优化：
class Solution {
public:vector<TreeNode*> allPossibleFBT(int n) {unordered_map<int, vector<TreeNode*>> memo;return generateFBT(n, memo);}private:vector<TreeNode*> generateFBT(int n, unordered_map<int, vector<TreeNode*>>& memo) {if (memo.find(n) != memo.end()) {return memo[n];}if (n % 2 == 0) {return {};}vector<TreeNode*> roots;if (n == 1) {roots.push_back(new TreeNode(0, nullptr, nullptr));return roots;}for (int left = 1; left <= n - 1; left += 2) {vector<TreeNode*> ltrees = generateFBT(left, memo);vector<TreeNode*> rtrees = generateFBT(n - left - 1, memo);for (auto ltree : ltrees) {for (auto rtree : rtrees) {TreeNode* root = new TreeNode(0, ltree, rtree);roots.push_back(root);}}}memo[n] = roots;return roots;}
};
这篇关于894. 所有可能的真二叉树（记忆性搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
