面试题库 › 算法 / 大模型 › 不同的二叉搜索树(LeetCode 96)

不同的二叉搜索树(LeetCode 96)

难度 ★★☆在 2 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

字节跳动1

常见岗位:推理部署与加速、C/C++ 软件开发

答案要点

  1. dp[i] 表示 i 个节点能构成的 BST 数量,只与节点数有关
  2. 枚举根 j:dp[i] = Σ dp[j−1] × dp[i−j],j 从 1 到 i
  3. 边界 dp[0] = 1、dp[1] = 1,时间 O(n²),空间 O(n)
  4. 结果是卡特兰数,可用 C(2n,n)/(n+1) 或递推 O(n) 计算
  5. 公式计算时注意先乘后除和整数溢出

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题