LeetCode 95. 不同的二叉搜索树 II （记忆化递归）

不同的二叉搜索树 II 思路： 对于一个序列，$l,l+1,l+2\dots \dots ，r-2,r-1,r$， 枚举每个值作为根节点， 然后它左边的数字构建左子树、右边的数字构建右子树，然后两两组合。 当然，也可以优化一下，进行记忆化递归。

/** * 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: map<pair<int,int>,vector<TreeNode*>> vis; vector<TreeNode*> generateTrees(int n) { if(n==0) return vector<TreeNode*>(0); return create(1,n); } vector<TreeNode*> create(int l,int r){ vector<TreeNode*> res; if(r-l<0){ res.push_back(nullptr); vis[make_pair(l,r)] = res; return res; } for(int val=l;val<=r;val++){ if(!vis.count(make_pair(l,val-1))){ vis[make_pair(l,val-1)] = create(l,val-1); } if(!vis.count(make_pair(val+1,r))){ vis[make_pair(val+1,r)] = create(val+1,r); } vector<TreeNode*> lc = vis[make_pair(l,val-1)]; vector<TreeNode*> rc = vis[make_pair(val+1,r)]; for(int i=0;i<lc.size();i++){ for(int j=0;j<rc.size();j++){ TreeNode* root = new TreeNode(val,lc[i],rc[j]); res.push_back(root); } } } return res; } };