不同的二叉搜索树

不同的二叉搜索树

 

 

详细思路

二叉树能用递归就用递归,递归定义好形参含义、返回的含义、函数的含义,返回的时机 枚举每一个值作为根结点,从这个根结点左边调用递归函数找到根结点左子树集合,从根结点右边调用递归函数找到根结点右子树集合,从两个集合中枚举并将根结点连接作为答案更新答案。想要利用递归函数找到根结点左子树集合,需要return找到的树集合,在start》end时需要return空集合   精确定义 dfs beg第一end最后的所有二叉搜索树的集合,如果beg>end空树{null},否则最后返回beg第一end最后的所有二叉搜索树的集合  
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return dfs(1,n);
    }
    vector<TreeNode*>dfs(int beg,int end){
        if(beg>end)return {nullptr};
        vector<TreeNode*>ans;
        for(int i=beg;i<=end;i++){
            vector<TreeNode*>allLeft,allRight;
            allLeft=dfs(beg,i-1);
            allRight=dfs(i+1,end);
            for(auto&oneLeft:allLeft){
                for(auto&oneRight:allRight){
                    TreeNode*root=new TreeNode(i,oneLeft,oneRight);
                    ans.push_back(root);
                }
            }
        }
        return ans;

    }
};
踩过的坑 递归函数定义重要性,
上一篇:python内置模块之string


下一篇:复原IP地址