莫非 - 技术博客
0%

leetcode 96 Unique Binary Search Trees

发表于 更新于 分类于

原题链接：Unique Binary Search Trees - LeetCode

题目

Given an integer n, return *the number of structurally unique **BST’*s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

img

1
2
Input: n = 3
Output: 5

Example 2:

1
2
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 19

方法1：动态规划

思路

首先想到二叉搜索树的定义，二叉搜索树左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值，且左右子树也分别是二叉搜索树。

回到本题，当给出n个节点，则根节点的值可以是1-n的任意一个。假设根节点的值为i，那么左子树就是由[1, i-1]这i-1个节点组成的二叉搜索树，右子树就由[i+1, n]这n-i个节点组成的二叉搜索树。

由此可见，原问题可以分解成规模较小的子问题，且子问题的解可以服用。因此，我们可以想到使用动态规划来求解本体。

算法

状态定义

dp[n]代表n个节点能组成不同二叉搜索树的数量

边界情况

当序列长度为 1（只有根）或为 0（空树）时，只有一种情况，即：
$$
dp[0]=1, dp[1]=1
$$
状态转移方程
$$
dp[n]=\sum_{i=1}^ndp[i-1]*dp[n-i]
$$
代码实现

1
2
3
4
5
6
7
8
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i+1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[-1]

复杂度分析

时间复杂度 : O(n^2)。

空间复杂度 : O(n)。

方法二：数学

思路与算法

在方法一中推导出的方程在数学上被称为卡塔兰数。卡塔兰数更便于计算的定义如下：
$$
C_0 =1, C_{n+1}=\frac{2(2n+1)}{n+2}C_n
$$

1
2
3
4
5
6
class Solution(object):
    def numTrees(self, n):
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

复杂度分析

时间复杂度 : O(n)。
空间复杂度 : O(1)。

参考

不同的二叉搜索树 - 不同的二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)