A solution via Catalan number


  • 0
    B

    A new thinking to solve this problem is that:
    For a given number of nodes, the number of total unique tree is an Catalan number (https://en.wikipedia.org/wiki/Catalan_number).

    Catalan Number: Cn = choose n from 2n / (1+n)

    And number of unique BST follows this rule.

    public int numTrees(int n) {
            int M = 2*n;
            int N = n;
            double c = 1;
            for(int i = 1; i <= N; i++)
            {
                c = c * (M-N+i)/i;
            }
            return (int) (c/(n+1));
        }
    

    Runtime: 0ms


Log in to reply
 

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