leetcode_【96】不同二叉搜索树

1.题目描述

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

示例:

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

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

2.解题思路

动态规划：

(1)初始化

n  = 1时，只含有1，1作为根节点，此时二叉搜索数个数为1；

(2) 算法

    （1）假设n个节点存在二叉排序树的个数是dp[i]，令f[i]为以i为根的二叉搜索树的个数，则
                dp[n] = f[1] + f[2] + f[3] + f[4] + ... + f[n] 

    （2）当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
                f [i]  = dp[i-1] * dp[n-i]

综合两个公式可以得到卡特兰数公式

>  dp[n] = dp[0] * dp[n-1] + dp[1] * dp[n-2]+...+dp[n-1] * dp[0]
>        = dp[n-1] * C(2n,n)
>        = dp[n-1] * (4*n-2)/(n-1)
>

3.代码

class Solution {
  public static int numTrees(int n) {
        //n个节点存在二叉树的个数
        long []dp = new long[n+1];
        //以i为根节点的二叉树个数
        dp[1] = 1;
        for(int i = 1;i<=n;i++){
            dp[i] = dp[i-1]*(4*i-2)/(i+1);
        }
        return (int) dp[n];
    }
}

4.提交记录