一、题目

题目链接：https://leetcode-cn.com/problems/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

二、分析及代码

采用动态规划解决，假设用G(n)表示前n个整数的二叉搜索树的总数，F（i）表示 当i节点为根节点的二叉搜索树的个数，则思考一下，当i为根节点时，由于二叉搜索树的规则，前i-1个节点都应该位于以i节点为根节点的左子树，i+1以后的节点都应该位于右子树，那么由咱们的假设可知，由前i-1个节点构成的左子树的二叉搜索树的总数为G(i-1)，同理右子树的二叉搜索树的总数为G（n-i），所以以i为根节点的二叉搜索树的总数F(i) = G(i-1)*G(n-i)，则前n个节点的所有二叉搜索树总数G(n） = F(1)+F(2)+...+F(n)。可以采用动态规划完成。代码如下：

class Solution: def numTrees(self, n: int) -> int: g = [1, 1] for i in range(2, n+1): t = 0 for j in range(1, i+1): t += g[j-1]*g[i-j] g.append(t) return g[-1]