Unique Binary Search Trees C++ solution


  • 0
    S

    structurally unique BST's is number of elements to right of it multiplied by number of elements to left of it
    n=1 output =1
    n=2 output =2
    n=3 output T(3)=T(2)+T(1)*T(1)+T(2)
    n=4 output T(4)=T(3)+T(2)*T(1)+T(1)*T(2)+T(3) and so on
    '''
    int numTrees(int n) {
    if(n<=2)
    return n;

        int count[n+1]={0};
        count[0]=1;
        count[1]=1;
        count[2]=2;
        for(int i=3;i<=n;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                count[i]+=count[j]*count[i-(j+1)];
            }
        }
        
            return count[n];
    }
    

    '''


Log in to reply
 

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