欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

96. 不同的二叉搜索树

程序员文章站 2022-04-22 11:41:47
不同的二叉搜索树给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 ......

不同的二叉搜索树

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路+代码+注释:

卡塔兰数列的递推式为:
96. 不同的二叉搜索树

public int numTrees(int n) {
            /*
            思路:n=0时为空树,因为空树也算是二叉查找树的一种所以个数为1
            n>=1时,二叉查找树的个数等于根节点左子树个数*根节点右子树个数
            dp[n]记录0~n对应的二叉查找树的个数

            dp[0]=1
            dp[1]=dp[0]*dp[0]
            n==2时,根节点可以是1和2
            dp[2]=dp[0]*dp[1]+dp[1]*dp[0]
            n==3时,根节点可以是1、2、3
            dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]

            由此可以推出卡塔兰数列的递推式

             */
            //加上n=0是n+1种情况
            int[] dp=new int[n+1];
            dp[0]=1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i+1]+=dp[j]*dp[i-j];
            }
        }
        return dp[n];
    }

本文地址:https://blog.csdn.net/qq_36059306/article/details/85986785