LeetCode 96 不同的二叉搜索树

LeetCode 96 不同的二叉搜索树"/>

LeetCode 96 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1
 

提示：

1 <= n <= 19

解题思路：

记忆化递归

不同的二叉搜索树 - 不同的二叉搜索树 - 力扣（LeetCode）

Python代码：

class Solution:@lru_cache(None)def numTrees(self, n: int) -> int:if n == 0:return 1if n == 1:return 1res = 0for i in range(1, n + 1):res += self.numTrees(i - 1) * self.numTrees(n - i)return res