LeetCode 96. 不同的二叉搜索树
题目描述
题意分析
使用数值为
1到n的全部节点，每个值恰好使用一次，统计能构成多少棵结构不同的二叉搜索树。只需要返回数量，不需要创建或返回这些树。二叉搜索树要求左子树中的值都小于根，右子树中的值都大于根。选择根之后，左右两侧分别包含哪些值就已经确定；需要继续选择的，是各自的子树结构。
解法：Catalan 动态规划
核心思路
[!blue]
固定根的位置后，左侧较小的键只能放入左子树，右侧较大的键只能放入右子树。两侧各自可以独立构造，再连接到同一个根上，因此总数可以按根的位置分类计算。
定义
dp[nodes]表示由nodes个互不相同、有序的键构成二叉搜索树的方案数。这里不需要记录键的具体起止值：同样数量的有序键可以按排名一一对应，数值整体变大或变小不会改变可用的结构。选择第
root个键作根时，左子树有root - 1个节点，右子树有nodes - root个节点。任意一种左子树都能与任意一种右子树配对，因此这个根贡献dp[root - 1] * dp[nodes - root]种方案。不同根得到的树不会相同，把所有根的贡献相加即可。令
dp[0] = 1，表示空子树是一种合法的选择，而不是没有方案。当根位于最左端或最右端时，一侧为空，仍应保留另一侧所有结构，乘以1才符合这个含义。按节点数从少到多计算，每次转移依赖的左右规模都小于当前规模，所需答案已经算出。这一递推得到的数列称为卡特兰数，最终返回
dp[n]。
解题步骤
- 创建长度为
n + 1的计数数组，初始化dp[0] = 1。- 依次计算
nodes = 1到n的结构数量。- 对每个规模枚举根的排名
root = 1到nodes，累加dp[root - 1] * dp[nodes - root]。- 返回
dp[n]。
代码实现
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
// 空子树也有一种构造，作为左右组合计数的乘法单位。
dp[0] = 1;
for (int nodes = 1; nodes <= n; nodes++) {
for (int root = 1; root <= nodes; root++) {
// 固定根后左右构造独立相乘，不同根的情况再相加。
dp[nodes] += dp[root - 1] * dp[nodes - root];
}
}
return dp[n];
}
}
func numTrees(n int) int {
dp := make([]int, n+1)
// 空子树也有一种构造，作为左右组合计数的乘法单位。
dp[0] = 1
for nodes := 1; nodes <= n; nodes++ {
for root := 1; root <= nodes; root++ {
// 固定根后左右构造独立相乘，不同根的情况再相加。
dp[nodes] += dp[root-1] * dp[nodes-root]
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(n^2)$，规模为
nodes时枚举nodes个根，总转移次数为 $1+2+\cdots+n$。- 空间复杂度：$O(n)$，保存
0到n共n + 1个规模的答案。
关键点总结
[!green]
- 子树结构数由节点数量决定，具体数值只需保持大小关系，无须额外记录区间。
- 同一个根下的左右方案独立组合，所以相乘；不同根对应互斥分类，所以求和。
dp[0] = 1是组合计数中的空选择，保证一侧为空的树也能正常计数。
易错点总结
[!yellow]
- 将
dp[0]留为0，会使涉及空子树的乘积归零，递推无法正确开始。- 把左右子树数量相加，会漏掉彼此配对的组合；把不同根的贡献相乘，则会把互斥情况错误组合。
- 枚举根时必须累加到
dp[nodes]，直接赋值只会保留最后一个根的贡献。- 根本身不属于任何一侧，左右节点数分别为
root - 1与nodes - root，两者之和为nodes - 1。- 题目要求精确数量，且
n <= 19时结果能放入 32 位有符号整数，不需要取模。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 95. 不同的二叉搜索树 II | 中等 | 同样枚举根并组合左右子树，本题用数量乘积代替实际构造树。 |
| 22. 括号生成 | 中等 | 两题的计数都满足卡特兰结构，可对比按根分割与按首个匹配括号分割。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！