0096. 不同的二叉搜索树.md

0096. 不同的二叉搜索树

• 标签：树、二叉搜索树、数学、动态规划、二叉树
• 难度：中等

题目大意

给定一个整数 n，求以 1 到 n 为节点构成的「二叉搜索树」有多少种？

解题思路

动态规划求解。

1 到 n 的每个节点都可以用来做根节点。每一个根节点 i 都是由左子树 (1, 2, ..., i - 1) 和右子树 (i + 1, i + 2, ..., n) 构成的。则二叉搜索树的个数肯定是两个子树个数的乘积。而根节点有 n 个，最终将这些个数累加起来即可。

定义 f[i] 为以 i 为根节点的二叉搜索树个数，dp[i] 为 i 个节点构成的二叉搜索树个数。则：

dp[i] = f(1) + f(2) + ... + f(i)。

当 i 为根节点时，其左子树节点个数为 i - 1，右节点个数为 n - i。则：

f(i) = dp[i - 1] * dp[n - i]。

则总和上述公式可定义状态 dp[i] 表示： i 个节点构成的二叉搜索树个数。

状态转移方程为 dp[i] = dp[0] * dp[i - 1] + dp[1] * dp[i - 2] + ... + dp[i - 1] * dp[0]。

即：dp[i] += dp[j - 1] * dp[i - j]，其中 1 ≤ j ≤ i。

代码

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        dp[0] = 1
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[n]