不同的二叉搜索树(LeetCode 96)
哪些公司问过
答案要点
- dp[i] 表示 i 个节点能构成的 BST 数量,只与节点数有关
- 枚举根 j:dp[i] = Σ dp[j−1] × dp[i−j],j 从 1 到 i
- 边界 dp[0] = 1、dp[1] = 1,时间 O(n²),空间 O(n)
- 结果是卡特兰数,可用 C(2n,n)/(n+1) 或递推 O(n) 计算
- 公式计算时注意先乘后除和整数溢出
易错点
- 把 dp[0] 设成 0,导致结果全错
- 以为结果和节点具体值有关
- 用卡特兰公式时先除后乘,产生取整误差
面试官常见追问
- 如果要求输出所有不同的 BST(LeetCode 95)呢?
- 为什么 dp[0] 要设成 1?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场