Didvide and Conquer concise solution


  • 0
    X
        vector<TreeNode*> dfs(int begin,int end)
        {
            vector<TreeNode*> res;
            if(begin>end)
                res.push_back(NULL);
            for(int i=begin;i<=end;i++)
            {
                vector<TreeNode*> left=dfs(begin,i-1);
                vector<TreeNode*> right=dfs(i+1,end);
                for(int j=0;j<left.size();j++)
                {
                    for(int k=0;k<right.size();k++)
                    {
                        TreeNode* root=new TreeNode(i);
                        root->left=left[j];
                        root->right=right[k];
                        res.push_back(root);
                    }
                }
            }
            return res;
        }
        
        vector<TreeNode*> generateTrees(int n) 
        {
            if(n<=0)
                return {};
            return dfs(1,n);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.