Recursive cpp solution with clear explanation


  • 0
    C
    class Solution {
    public:
    
        // generateBST(i, j) = 
        // i when i=j
        // k, k.left = if k-1<i. NULL, else. generateBST(i, k-1), k.right = if k+1>j. NULL, else. generateBST(k+1, j), i<=k<=j
        
        vector<TreeNode*> generateBST(int i, int j)
        {
            vector<TreeNode*> result;
            
            if(i == j) 
            {
                result.push_back(new TreeNode(i));
                return result;
            }
            
            for(int k=i; k<=j; k++)
            {
                vector<TreeNode*> lvec;
                if(k-1 < i) lvec.push_back(NULL);
                else        lvec = generateBST(i, k-1);
                
                vector<TreeNode*> rvec;
                if(k+1 > j) rvec.push_back(NULL);
                else        rvec = generateBST(k+1, j);
                
                for(int li=0; li < lvec.size(); li++)
                {
                    for(int ri=0; ri < rvec.size(); ri++)
                    {
                        TreeNode *root = new TreeNode(k);
                        root->left = lvec[li];
                        root->right = rvec[ri];
                        result.push_back(root);
                    }
                }
            }
            
            return result;
        }
    
        vector<TreeNode*> generateTrees(int n) 
        {
            return generateBST(1, n);
        }
    };

Log in to reply
 

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