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;
    }