给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3
输出:5
示例 2:
输入:n = 1
输出:1
#最直观的思路
res[i]保存i在满足条件下的搜索树种数
res[i] += (res[j-1] * res[i-j])
j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量
class Solution:
def numTrees(self, n: int) -> int:
res = [0] * (n + 1)
res[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
res[i] += (res[j-1] * res[i-j])
return res[n]