不同的二叉搜索树_

忆水寒

class Solution {
public:
    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 = 1; j<=i; j++)
                dp[i] += dp[i-j]*dp[j-1];
        }
        return dp[n];
    }
};

发表于 2016-09-08 23:16:20 回复(0)

hardy

 public static int numTrees(int n){
    	if(n<0){
    		return -1;
    	}
    	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];
    }

我设dp[i]表示共有i个节点时，能产生的BST树的个数 
n == 0 时，空树的个数必然为1，因此dp[0] = 1 
n == 1 时，只有1这个根节点，数量也为1，因此dp[1] = 1 
n == 2时，有两种构造方法，如下图所示： 
加载中...
因此，dp[2] = dp[0] * dp[1] + dp[1] * dp[0] 
n == 3时，构造方法如题目给的示例所示，dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0] 
同时，当根节点元素为 1, 2, 3, 4, 5, ..., i, ..., n时，基于以下原则的BST树具有唯一性： 
以i为根节点时，其左子树构成为[0,...,i-1],其右子树构成为[i+1,...,n]构成 
因此，dp[i] = sigma（dp[0...k] * dp[k+1...i]） 0 <= k < i - 1

编辑于 2016-08-29 21:48:55 回复(3)

NBingGee

//选择一个节点，它的左右子树个数的乘积就是总的个数，可以递归解决
class Solution {
public:
    int numTrees(int n) {
        if(n <= 1)
            return 1;
        int uniqueBST = 0;
        for(int i = 1; i <= n; i++){
            uniqueBST += numTrees(i-1)*numTrees(n-i);
        }
        return uniqueBST;
    }
};

发表于 2016-09-11 10:45:43 回复(1)

牛客6142959号

    int numTrees(int n) {
        //参考卡特兰数
        //递推公式：令h(0)=1,h(1)=1，catalan数满足递推式[2]  ：
//h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)
//例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
//h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
//另类递推式[3]  ：
//h(n)=h(n-1)*(4*n-2)/(n+1);
        int dp[n];
        dp[0]=1;
        for(int i=1;i<=n;i++)
            dp[i]=dp[i-1]*(4*i-2)/(i+1);
        return dp[n];
    }

发表于 2017-09-22 20:05:17 回复(2)

c++好难

class Solution {
 public:
     int numTrees(int n) {
         if(n<=1) return 1;
         vector<int> res(n+1,0);
         res[0]=1;
         res[1]=1;
         for(int i=2;i<n+1;++i){
             for(int j=0;j<i;++j){
                 res[i]+=res[j]*res[i-1-j];
             }
         }
         return res[n];
     }
 };

编辑于 2018-06-28 20:33:48 回复(1)

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)

我要成为牛豪

1.定义dp[i] 含义，一般是问什么定义成什么

2.状态转移方程，dp[i] 怎么由别的状态计算

3.初始化dp[]数组

4.迭代的方向

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    public int numTrees (int n) {
        // write code here
        int[] dp = new int[n+1];           //i 能构成的二叉搜索树数目
        dp[0]=1;dp[1]=1;                //初始化，注意 0 的时候赋值 1 
        for(int i=2;i<n+1;i++){        //从小到大遍历
            for(int j=1;j<=i;j++){
             dp[i]+=dp[i-j]*dp[j-1];    //状态转移方程：左子树所有情况*右子树所有情况
            }
        }
        return dp[n];
    }
}

时间O(n²)

空间O(n)

编辑于 2021-12-03 08:39:16 回复(0)

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)

C/C++

努力的牛牛

    /*
    * 目的：求BST的数量
    * 方法：动态规划
    */
    int numTrees(int n) {
        if (n<0) 
            return -1;
        vector<int>vec(n+1);
        vec[0] = 1;
        vec[1] = 1;
        for (int i = 2;i<=n;++i){
            for (int j = 0;j<i;++j){
                vec[i] += vec[j]*vec[i-j-1];
            }
        }
        return vec[n];
    }

发表于 2019-12-08 15:34:56 回复(0)

我只是个菜鸡

不同的二叉搜索树unique-binary-search-trees

思路：暴力递归 or 动态规划

解法一：暴力递归

每次递归都遍历1~n中的数，并选当前的数作为根，判断它的左子树和右子树能有多少种组合
当前数作为根能够得到的二叉搜索树个数是其左子树能够构成的二叉搜索树个数与右子树能够构成的二叉搜索树个数的笛卡尔积
f(i) = f(i-1)* f(n-1)

代码

    public int numTrees(int n) {
        if(n<=1)
            return 1;
        int res = 0;
        for(int i=1;i<=n;i++){
            res+=numTrees(i-1)*numTrees(n-i);
        }
        return res;
    }

解法二：动态规划

创建一维int数组dp[]，dp[i]表示1-i数字能组成多少种二叉搜索树
由递归的递归式可以推出状态转换方程
dp[ i ] = dp[ i ]+dp[ j-1] * dp[ i-j ]，j表示在其左子树或右子树选的根的位置

代码

    public int dp(int n){
        int[] dp = new int[n+1];
        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];
    }

发表于 2019-08-22 13:34:18 回复(0)

tuweilong

/*
动态规划。
dp[i]表示i个节点时，种类数。
二叉排序树的中序遍历是递增序列。
取不同根节点时，肯定为不同的树，该大类树的种树等于左子树种类*右子数种类。
*/
public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[0] = 1;
        for (int m = 2; m <= n; m++)
            for (int i = 1; i <= m; i++) {
                dp[m] += dp[i - 1] * dp[m - i];
            }
        return dp[n];
    }
}

发表于 2019-06-20 16:30:36 回复(0)

LeBronWitness

public class Solution {
    public int numTrees(int n) {
        int[] store=new int[n+1];
        store[1]=1;
        for(int i=2;i<=n;i++) {
            for(int j=1;j<=i;j++) {
                if(j==1||j==i) store[i]+=store[i-1];
                else store[i]+=store[i-j]*store[j-1];
            }
        }
        return store[n];
    }
}

发表于 2019-05-02 09:30:59 回复(0)

进击的雨滴

//动态规划思想：维护一个数组来存储n = i时候的BST的个数。这样的话给定一个数n，可以分为多种情况，
//若根节点是n,那个它就没有右子树，左子树最有n-1个节点，若根节点为i，那么左子树有i-1个节点，右子树有i+1个节点;
//建立递归表达式:![图片说明](https://uploadfiles.nowcoder.com/files/20190221/417614_1550753757588_equation?tex=f(x)%3D%5Cleft%5C%7B1%EF%BC%8C%E5%A6%82%E6%9E%9Cn%20%3D%3D%201%3B%202%2C%E5%A6%82%E6%9E%9Cn%3D%3D2%3B%20f(x-1)%2Bf(1)*f(x-2)%2B...%2Bf(x-1)%5Cright%5C%7D "图片标题") 
class Solution {
public:
    int numTrees(int n) {
        if (n == 0)
            return 0;
        vector<int> vec{ 1,2 };
        for (int i = 3; i <= n ;i++)
        {
            int count = 0;
            for (int j = 0; j < i; j++)
            {
                if (j == 0 || j == i-1)
                {
                    count += vec[i - 2];
                    continue;
                }
                count += vec[j-1] * vec[i - j - 2];
            }
            vec.push_back(count);    
        }
        return vec[n - 1];
    }
};

发表于 2019-02-21 20:58:20 回复(0)

为你扣下F键

//递归法
class Solution {
public:
    int numTrees(int n) {
        if(n==0)
         return 1;
        int res = 0;
        for(int i=0; i<n; ++i){
         res += numTrees(i)*numTrees(n-1-i);
  }
  return res;
    }
};
//非递归，创建一个数组，第i个值等于前i-1个数首尾相乘，然后向中间逼近
class Solution {
public:
    int numTrees(int n) {
        int* num = new int[n+1];
        num[0] = 1;
        for(int i=1; i<n+1; ++i){
            num[i] = 0;
            for(int j=0; j<i; ++j){
                num[i] += num[j]*num[i-1-j];
            }
        }
        return num[n];
    }
};

编辑于 2018-08-16 22:41:49 回复(0)

X_MAN

class Solution {
public:
    int numTrees(int n) {
        // catalan
        return int( factorial(2*n) / factorial(n) / factorial(n+1) );
    }
    
    double factorial(int n) {
        if (n == 1) return 1;
        
        return n * factorial(n-1);
    }
};

发表于 2017-11-06 15:01:45 回复(0)

C/C++

nbgao

class Solution {
public:
    int numTrees(int n) {
        if(n <= 1)
        	return 1;
        
        int sum = 0;
        for(int i=1;i<=n;i++)
        	sum += numTrees(i-1) * numTrees(n-i);
        	
        return sum;
    }
};

编辑于 2017-09-25 21:34:57 回复(2)

LinuX18

class Solution {
public:
    int numTrees(int n) 
    {
        if(n<=0)
            return 0;
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=i-1;j++)
                dp[i] += dp[j]*dp[i-1-j];
        }
        return dp[n];
    }
};

发表于 2017-07-14 20:43:57 回复(0)

我要吃油泼面

public class Solution {
    public int numTrees(int n) {
        if(n < 0)
            return -1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){ //i为当前节点值，
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];//dp[j]左子树种数，dp[i - j - 1]右子树种数
            }
        }
        return dp[n];
    }
}

发表于 2017-05-18 14:08:37 回复(0)

ridikuius

//BST树：以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。
//动态规划状态为count[n],count[n]表示到正整数i为止的BST个数 ;  public class Solution {
    public int numTrees(int n) {
          if (n < 0) {
            return -1;
        }

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

        return count[n];
    }
}

编辑于 2016-08-17 17:33:04 回复(0)

xiao_lai

class Solution {
public:
    int numTrees(int n) {
        //bool odd;  //是否是奇数的标示
        /*
        vector<int> array;
        array.push_back(1);  //f0=1
        array.push_back(1);   //f1=1
        array.push_back(2);  //f2=2
        array.push_back(5);   //f3=5
        for(int i=4;i<=n;i++){
            if((i&1)==1){
            	//odd = true;
                int half = i>>1;
                int sum=0;
                int j;
                for(j=0;j<half;j++){
                    sum += array[j]*array[i-1-j];
                }
                sum *= 2;
                sum += array[half]*array[half];
                array.push_back(sum);    //fn
        	}else{
            	//odd = false;
                int half = i>>1;
                int sum=0;
                for(int j=0;j<half;j++){
                    sum += array[j]*array[i-1-j];
                }
                array.push_back(2*sum);    //fn
        	}
        }
        return array[n];
        */
        
        
        //方式二：如果了解卡特兰数列的话，其实二叉搜索树的形态结构树就是一个卡特兰数列
        //直接套用公式计算 h(n)=C(2n,n)/(n+1)={2n(2n-1)(2n-2)...(n+2)}/{n(n-1)(n-2)...1}  组合数需要计算阶乘
        //可以采用递推公式  h(n)=(4n-2)/(n+1)*h(n-1) 来计算
        int fn_1 = 1,fn;
        if(n==1)return fn_1;
        for(int i=2;i<=n;i++){
            fn = (float)(4*i-2)/(i+1)*fn_1;
            fn_1 = fn;
        }
        return fn;
    }
};

发表于 2016-06-27 19:08:49 回复(0)

不同的二叉搜索树

输入

输出

不同的二叉搜索树unique-binary-search-trees

思路：暴力递归 or 动态规划

解法一：暴力递归

代码

解法二：动态规划

代码

问题信息

热门推荐

通过挑战的用户

相关试题