[二叉搜索树][递归]leetcode95：不同的二叉搜索树Ⅱ(medium)

递归]leetcode95：不同的二叉搜索树Ⅱ(medium)"/>

[二叉搜索树][递归]leetcode95：不同的二叉搜索树Ⅱ(medium)

题目：

题解：

• 分治法
• 每次根据根节点i来划分左右子树，[1,i-1]为所有左子树的集合，[i,n]为所有右子树的集合，等到区间内没有元素时，分治法的最小子问题解决，那么左右子树的集合也得解了。

代码如下：

class Solution {
public:vector<TreeNode*> generateTrees(int n) {if(n==0)return {};return helper(1,n);}vector<TreeNode*> helper(int begin,int end){vector<TreeNode*> result;if(begin>end)//此时没有数字{result.push_back(nullptr);return result;}for(int i=begin;i<=end;++i){//i作为根节点，然后分为左子树的数字范围[begin,i-1]，右子树的数字范围[i,end]//当区间内没有元素时，最小子问题解决，那么左右子树的集合也得解了vector<TreeNode*> left_trees=helper(begin,i-1);//得到左子树的集合vector<TreeNode*> right_trees=helper(i+1,end);//得到右子树的集合//左右子树两两组合for(auto l:left_trees){for(auto r:right_trees){TreeNode* root=new TreeNode(i);//数字i作为根节点root->left=l;root->right=r;result.push_back(root);}}}return result;}};