我要招人

去企业版

首页 > 试题广场 >

不同的二叉搜索树

[编程题]不同的二叉搜索树

热度指数：13861 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个值n，能构建出多少不同的值包含1...n的二叉搜索树（BST）？

例如

给定 n = 3, 有五种不同的二叉搜索树（BST）

示例1

输入

输出

算法知识视频讲解

Java

LiberHome

必须要吐槽一下：这是简单题？？？怕是对简单有什么误解吧

方法1：时间复杂度O(n²)

   
public class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

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

方法2：

今天下午的时间用来纪念一下 Eugène Charles Catalan。。有高考内味，没错了 Catalan数-组合数学

   
public class Solution {
    public int numTrees(int n) {
       long Catalan = 1;
       for(int i = 0; i < n; i++){
           Catalan = 2*(2*i+1)*Catalan/(i+2);
       }
       return (int)Catalan;
    }
}

编辑于 2020-07-12 17:25:19 回复(0)

Java

科学xx

    //递归 递推公式：f(n) = f(i)*f(n-i) +...  (i=0),f(0) = 1;    public int numTrees (int n) {
      if (n == 0){
            return 1;
        }
        int d = 0;
        for (int i = 0; i < n; i++) {
            d += numTrees(i)*numTrees(n-i-1);
        }
        return d;
    }


//循环
public int numTrees (int n) {
     int[] d = new int[n+1];
        d[0] = 1;
        d[1] = 1;
        for (int i = 2; i < n+1; i++) {
            for (int j = 0; j < i; j++) {
                d[i] += d[j]*d[i-j-1];
            }
        }
        return d[n];
    }

发表于 2020-06-29 20:02:50 回复(0)

Java

齐鱼鱼

    public static int numTrees(int n) {         int[] dp=new int[n+1];         dp[0]=1;         dp[1]=1;         for(int i=2;i<=n;i++){             for(int j=0;j<i;j++){                 dp[i]+=dp[j]*dp[i-j-1];             }         }         return dp[n];     }
for example:
dp[3]=dp[0]dp[2]+dp[1]dp[1]+dp[2]dp[0]

发表于 2018-09-06 15:10:02 回复(0)

Java

傻傻傻傻

/**
卡特兰数(Catalan)的应用
*/
public class Solution {
    public int numTrees(int n) {
        if (n == 0 || n == 1) return 1;
        int[] result = new int[n+1];
        result[0] = result[1] = 1;
        //result[n] = result[0]*result[n-1] + result[1]*result[n-2] + ...
        // + result[n-1]result[0];
        for (int i = 2; i <= n; i++)
            for (int j = 0; j <= i-1; j++)
                result[i] += result[j]*result[i-j-1];
        return result[n];
    }
}

编辑于 2017-11-29 18:19:14 回复(0)

Java

卖萌の哈士奇

    //左边可能的数量乘以右边可能的数量
    public int numTrees(int n) {
        if(n == 0 || n == 1) return 1;
        int sum = 0;
        for(int i = 0; i <= n - 1; i++){
            sum += numTrees(i) * numTrees(n - 1 - i);
        }
        return sum;
    }

发表于 2017-08-22 14:23:42 回复(0)

Java

Zfirsty

//和ii一样的思路
public class Solution {
    public int numTrees(int n) {
        return f(1,n+1);
    }
    public int f(int low,int high){
        if(low>=high) return 1;
        int sum=0;
        for(int i=low;i<high;i++){
            int left=f(low,i);
            int right=f(i+1,high);
            sum+=left*right;
        }
        return sum;
    }
}

发表于 2017-07-31 11:08:59 回复(0)

Java

sc111

递归

1.维护一个res,res的结果是每一个数字作为头结点的种类的加和

2.每一个节点的种类数目等于左子树的个数乘以右子树的数目

3.对于头结点是i，左子树树种类是numTrees(i-1)，右子树种类是numTrees(n-i)

public class Solution {

public int numTrees(int n) {

if(n == 0)

return 1;

if(n == 1)

return 1;

if(n == 2)

return 2;

int res = 0;

for(int i=1;i<=n;i++)

res += numTrees(i-1) * numTrees(n-i);

return res;

}

发表于 2017-06-15 16:30:51 回复(1)

Java

油头教授的坩埚

/**
 * Taking 1~n as root respectively: * 1 as root: # of trees = F(0) * F(n-1)  // F(0) == 1 * 2 as root: # of trees = F(1) * F(n-2) 
 * 3 as root: # of trees = F(2) * F(n-3)
 *      ...
 * n-1 as root: # of trees = F(n-2) * F(1)
 * n as root: # of trees = F(n-1) * F(0)
 *
 * So, the formulation is: *      F(n) = F(0) * F(n-1) + F(1) * F(n-2) + F(2) * F(n-3) + ... + F(n-2) * F(1) + F(n-1) * F(0)
 */ int numTrees(int n) { int dp[n+1];
    dp[0] = dp[1] = 1;
    for (int i=2; i<=n; i++) {
        dp[i] = 0;
        for (int j=1; j<=i; j++) {
            dp[i] += dp[j-1] * dp[i-j];
        }
    }
    return dp[n];
}

发表于 2017-03-12 11:18:20 回复(0)

Java

城市里的养猫者

public int numTrees(int n) { int [] G = new int[n+1];
    G[0] = G[1] = 1; for(int i=2; i<=n; ++i) { for(int j=1; j<=i; ++j) {
    		G[i] += G[j-1] * G[i-j];
    	}
    } return G[n];
}