LeetCode Problem 96-Unique Binary Search Trees

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

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

思路一

动态规划解决,假设 表示长度为 的序列的BST的数目, 表示以第 个结点为根结点的BST的数目,则可以发现: 特殊的,有

并且,给定一个序列 1 到 ,选择 作为根结点的BST的数目 就是其左子树的数目与右子树的数目的乘积,举例来说, 以 3 为根结点的BST的数目,为了构建以 3 为根结点,序列为 的BST,需要构建左边序列 的BST,以及右边序列 的BST,然后再将两者结合(即两者的笛卡尔积),值得注意的是,左边的BST的数目可以记作 ,而右边的BST的数目则可以记作 ,即

因此,有 结合上述两个公式,有 故可以通过动态规划计算 ,代码如下:

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[n]

相似问题

  1. Unique Binary Search Trees II
此时不赞何时赞!