Simple 20 line function C++ Recursive


  • 0
    A
    class Solution {
    public:
        vector<TreeNode*>generateTrees (int n) {
            vector<TreeNode *>ans ;
            if(n==0)
                return ans;
            ans = NumberOfBST(1,n) ; 
            return ans;
        }
        inline vector<TreeNode*> NumberOfBST(int st , int A) {
    		vector<TreeNode*>tmp;
    		if(st>A){
    			tmp.push_back(NULL);
    			return tmp;
    		}
    		for(int i=st ;i <= A ; i++){
    			TreeNode *root = new TreeNode(i);
    			vector<TreeNode*>left = NumberOfBST(st,i-1);
    			vector<TreeNode*>right = NumberOfBST(i+1,A);
    			for(int j=0;j<(int)left.size();j++){
    				for(int k=0;k<(int)right.size();k++){
    					TreeNode *curr = new TreeNode(i);
    					curr->left = left[j];
    					curr->right = right[k];
    					tmp.push_back(curr);
    				}
    			}
    		}
    		return tmp;
        }
    };
    

Log in to reply
 

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