leetcode96不同的二叉搜索樹

leetcode96:不同的二叉搜索樹

題目描述

給你一個整數 n ，求恰由 n 個節點組成且節點值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數。

輸入輸出樣例

輸入：n = 3
輸出：5

輸入：n = 1
輸出：1

算法一：使用動態規劃

    //二叉搜索樹的定義：若其左子樹不為空，則左子樹上所有的結點的值均小於他的根結點，若他的右子樹不空，則右子樹上所有的節點的值均大於他的根節點的值
   //其左右子樹也為二叉查找樹 
    int numTrees(int n)
    {
    
        //建立動態規劃數組
        vector<int>dp(n+1,0);
        //設定初始條件
        dp[0]=1;
        dp[1]=1;
        //設定轉換的方程
        for(int i=2;i<=n;i++)
        {
    
            for(int j=1;j<=i;j++)
            {
    
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

算法二：使用格蘭數的定義

//卡塔蘭數
    int numTrees2(int n)
    {
    
        long long c=1;
        for(int i=0;i<n;i++)
        {
    
            c=c*2*(2*i+1)/(i+2);
        }
        return (int)c;
    }