递归]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;}};
更多推荐
[二叉搜索树][递归]leetcode95:不同的二叉搜索树Ⅱ(medium)
发布评论