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
。
代码 #
|
|