[LeetCode]96. 不同的二叉搜索树(Unique Binary Search Trees)

题目描述

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

示例:

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

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

解题思路

动态规划。
假设第 n 个节点存在的二叉搜索树的个数为 $G(n)$,设 $f(i)$ 表示以 i 为根的二叉搜索树的数量,有:

而以 i 为根节点时,其种数等于左右子树的种数之积:

故:

叫做卡特兰数。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
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]

执行用时 : 80 ms
内存消耗 : 13.8 MB

参考

https://leetcode-cn.com/problems/unique-binary-search-trees/solution/hua-jie-suan-fa-96-bu-tong-de-er-cha-sou-suo-shu-b/