1. 一眼看穿题目本质是计数问题不是构造问题1.1 题目到底在问什么很多朋友第一次看到96. 不同的二叉搜索树这个标题时第一反应是去枚举各种树形结构结果越枚举越乱。其实这道题问的并不是怎么把二叉搜索树构造出来而是给定 1 到 n 这 n 个节点能构成多少种结构互不相同的二叉搜索树。关键在于结构不同这四个字。二叉搜索树的性质是左子树的所有节点值都小于根右子树的所有节点值都大于根。当节点值固定为 1 到 n并且要求中序遍历结果是升序时一棵二叉搜索树的形态其实完全由它的左右子树的形态组合决定。也就是说我们数的不是节点的排列方案而是树的拓扑结构方案。这个问题如果靠暴力枚举复杂度是指数级别的。n 3 时还能手画n 4 时画出 14 种已经有点吃力n 5 时是 42 种等你画到 n 10 就要面对 16796 种结构了。所以这道题真正的考察点是你能不能从枚举树形的惯性思维里跳出来看到它背后的递推结构。1.2 关键突破口枚举根节点的位置我把这个问题的突破口概括成一句话不要想整棵树只想根节点。假设现在有 1 到 n 共 n 个节点我们任选其中一个值 k 作为根节点。根据二叉搜索树的定义左子树里只能放比 k 小的节点也就是 1 到 k-1共 k-1 个节点右子树里只能放比 k 大的节点也就是 k1 到 n共 n-k 个节点。这一步看起来平平无奇但它带来一个非常强的结论左子树能构成的形态数量只取决于左子树的节点个数也就是 k-1而不取决于这些节点的具体值。同理右子树能构成的形态数量只取决于 n-k。你可能会有疑问左子树的值是 1 到 k-1右子树的值是 k1 到 n两组值不一样为什么形态数量只和个数有关答案是二叉搜索树的形态只依赖于节点的相对大小关系不依赖于绝对数值。1、2、3 三个节点能构成的 5 种 BST 形态和 5、6、7 三个节点能构成的形态是一模一样的。理解这一点是整个动态规划推导的基础。1.3 为什么不能直接套排列组合公式有人说既然左子树、右子树都是子问题那我是不是可以直接用组合数 C(n, 2) 之类的方法来算不行。这里面的误区在于树的高度和节点分布并不是均匀的不存在简单的从 n 个位置里选两个子树边界这种均匀结构。二叉搜索树的每一种形态本质上都是从根节点开始递归地把节点划分到左右子树的结果。这个递归划分的次数、每次划分的子树规模都不一样所以它天生适合用递推或者递归来描述而不是直接的组合公式。卡特兰数公式确实存在但它也是从递推关系推导出来的而不是凭空套上去的。想通这一点整个问题的难度就下降了一大半。2. 动态规划推导自底向上把树数出来2.1 dp[i] 的定义与初始化我们把问题抽象成dp[i] 表示由 i 个节点能构成的不同二叉搜索树的形态数量。这里有一个非常容易忽略但极其重要的初始化dp[0] 1。为什么 0 个节点也算一种形态因为空树是一棵合法的树。更关键的是当根节点的左子树为空即 k 1或者右子树为空即 k n时空子树必须被视作一种形态否则乘法原理无法成立。我们可以用一个生活化的类比来理解你给一个书架分层左边放几本、右边放几本。如果左边一本都不放这本身也是一种合理的摆放方案不能因为书架上没有书就认为这层不存在。dp[0] 1 就是这个意思。dp[1] 呢只有一个节点的树左子树为空、右子树为空形态只有一种所以 dp[1] 1。这两个初始值一个代表空一个代表单节点是后面所有递推的基础。2.2 状态转移方程的几何意义当我们要计算 dp[n] 时可以从 1 到 n 逐个枚举根节点的值 k。对于每一个 k左子树有 k-1 个节点能构成 dp[k-1] 种形态右子树有 n-k 个节点能构成 dp[n-k] 种形态左右子树各自的形态互相独立所以组合起来是 dp[k-1] * dp[n-k] 种。把所有 k 的情况加起来就得到dp[n] sum(dp[k-1] * dp[n-k])其中 k 从 1 到 n如果令 j k-1那么 n-k n-j-1上式可以等价写成dp[n] sum(dp[j] * dp[n-j-1])其中 j 从 0 到 n-1这两个写法本质一样后面那个在代码里更常用。我建议你记住后面这种因为 j 直接代表左子树节点数边界特别好处理。这里为什么可以用乘法因为左子树的每一种形态都可以和右子树的任意一种形态配合形成一棵新的完整的树而且这些配合不会产生重复。为什么不会重复因为根节点的值 k 被明确枚举了不同的 k 会产生不同的根节点所以整棵树一定是不同的。这个按根节点分类的思路保证了不重不漏。2.3 手算 dp[0] 到 dp[4] 的完整过程光看公式容易觉得抽象我把前几项展开算一遍你感受一下递推的节奏。已知dp[0] 1 dp[1] 1计算 dp[2]dp[2] dp[0]*dp[1] dp[1]*dp[0] 1*1 1*1 2这两项分别对应根节点为 1 和 2 的情况结果是 2。手动验证一下两个节点的 BST 只有根 1、右孩子 2和根 2、左孩子 1两种形态正确。计算 dp[3]dp[3] dp[0]*dp[2] dp[1]*dp[1] dp[2]*dp[0] 1*2 1*1 2*1 5当根为 1右子树 2 个节点有 2 种形态根为 2左右各 1 个节点各只有 1 种形态组合出来 1 种根为 3左子树 2 个节点有 2 种形态。合计 5 种。计算 dp[4]dp[4] dp[0]*dp[3] dp[1]*dp[2] dp[2]*dp[1] dp[3]*dp[0] 1*5 1*2 2*1 5*1 14到这里你应该能清楚看到趋势1, 1, 2, 5, 14——这就是卡特兰数的前几项。到这一步你已经不是在画树了而是在用递推直接数树。2.4 参考实现先看最直觉的二维版本虽然本题用不到二维 DP但理解这个版本有助于把握思路# 二维 DP 版本先枚举区间长度再枚举左子树大小 def num_trees(n): dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): for j in range(i): dp[i] dp[j] * dp[i - j - 1] return dp[n]内层循环里的j就是左子树节点数i - j - 1是右子树节点数。这个实现的时间复杂度是 O(n²)空间复杂度是 O(n)。如果你用 C需要注意dp数组的类型n 到 19 左右答案就会超过 int 范围后面详细说long long numTrees(int n) { vectorlong long dp(n 1, 0); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { for (int j 0; j i; j) { dp[i] dp[j] * dp[i - j - 1]; } } return dp[n]; }Java 里同样可以用long[]这个解法已经足够通过本题。3. 从 DP 到卡特兰数一个数学公式的跃迁3.1 卡特兰数到底是什么如果只是解这一道题上面的动态规划已经足够了。但很多刷题的朋友会在题解区看到卡特兰数四个字然后陷入疑惑这个数列到底是怎么从二叉搜索树里冒出来的卡特兰数是一个非常经典的组合数学数列它描述了一大类递归拆分结构的总数。除了二叉搜索树以下这些问题的答案也都是卡特兰数n 对括号的合法排列数1 到 n 的入栈顺序对应的合法出栈序列数n 个节点的二叉树不要求二叉搜索树总形态数在 n x n 的网格中从 (0,0) 走到 (n,n)不越过对角线的路径数。为什么这么多不同的问题会共享同一个答案序列因为它们骨子里的结构是等价的。以括号序列为例一对括号把序列分成内部和外部两部分这种嵌套-并列的递归结构和二叉搜索树里根节点把序列分成左右子树的结构完全一致。你在二叉搜索树里数的是形态在括号问题里数的是序列本质上是同一个递归拆分的计数。理解这一层你就能做到会一道题通一类题。3.2 从递推公式推导出通项公式卡特兰数最常见的递推形式是C(0) 1 C(n) sum(C(i) * C(n-1-i))i 从 0 到 n-1这和我们前面写的dp[n] sum(dp[j] * dp[n-j-1])一字不差。所以二叉搜索树问题的答案就是第 n 个卡特兰数。卡特兰数的通项公式是C(n) C(2n, n) / (n 1)这个公式也叫组合数封闭形式。怎么理解它的来历一个经典的证明思路是从括号序列或走网格路径的角度利用反射原理算出非法情况的数量然后用总数减去非法数。结合二叉搜索树来证明通项公式比较绕一个是 dp 递推一个是组合计数两者殊途同归但考场上更实际的用法是直接用通项公式来 O(n) 计算答案。为什么通项公式能成立我给你一个直觉上的解释在 2n 个位置里选 n 个作为某种标记总共有 C(2n, n) 种情况但其中有一部分是不合法的因为过程中某一刻会打破平衡。反射原理把这部分非法情况一一对应到 C(2n, n-1) 种情况所以合法的数量是 C(2n, n) - C(2n, n-1)化简后正好等于 C(2n, n) / (n1)。这个证明在括号序列模型里最容易理解建议你从那里入手比直接从二叉搜索树硬证要轻松得多。3.3 O(n) 计算组合数与连乘化简如果直接在代码里算组合数 C(2n, n)可以先用公式展开C(2n, n) (2n)! / (n! * n!)但阶乘在 n 稍大时会爆炸必须边乘边除。更稳妥的写法是用循环累乘def num_trees(n): result 1 for i in range(n): result result * (2 * n - i) // (i 1) # 现在 result C(2n, n) return result // (n 1)这里有一个特别容易踩的坑result result * (2*n - i) // (i 1)不能把除法提前到乘法之前否则会丢失精度。因为每一步的乘法结果一定能够被i 1整除这是组合数 C(2n, i1) 的递推性质保证的。只要保证先乘后除整数除法就不会产生小数误差。还有另一种写法直接从卡特兰数相邻两项的关系出发C(n) C(n-1) * (4*n - 2) / (n 1)这个递推式也很常用计算时同样注意先乘后除def num_trees(n): c 1 for i in range(1, n 1): c c * (4 * i - 2) // (i 1) return c我个人在刷题时会优先用组合数循环版本因为它在很多其他组合问题里也能复用写起来不容易错。3.4 DP 方案与通项方案的复杂度对比一张表看明白两种方案的取舍方案时间复杂度空间复杂度代码量适用场景动态规划O(n²)O(n)约 10 行任何 n思路直观不易错卡特兰通项O(n)O(1)约 8 行大 n追求效率时使用从 LeetCode 这道题的约束看n 最大是 19O(n²) 的 DP 完全够用。但如果你在其他地方遇到 n 高达几千的变体题就必须用 O(n) 的通项公式了。另外通项公式里涉及long long的乘法需要注意溢出后面我会专门讲。4. 刷题过程中的常见坑与实用经验4.1 类型溢出C(34,17) 就已经超过 int 范围这道题 n 虽然只有 19但中间结果很容易超 int。算一下第 19 个卡特兰数是多少C(19) 1767263190这个数刚好在 int 正数范围内但你再算下一个C(20) 6564120420已经超过 2^31 - 1 2147483647 了。如果你用int类型存 dp 数组在 n 19 时答案本身不会爆但在中间计算dp[j] * dp[i-j-1]时两个 int 相乘可能先溢出再赋值给 int结果就会错。所以稳妥起见dp 数组统一用long long即 64 位整数。Python 的用户没有这个烦恼因为它的整数是无限精度的但 C/Java 的用户必须注意。如果题目把 n 范围改大到 30 以上连long long都可能不够这时需要考虑取模输出或者用 Python 这类大整数语言。刷题时先看一眼 n 的范围再决定类型是基本素养。4.2 dp[0] 1 的地位比想象中更重要我自己第一次做这道题时把 dp[0] 初始化为 0结果整个 dp[2] 都算成了 0想了半天没搞明白。dp[0] 1 不是凭空多出一种树而是在表达空子树是一种合法的子树形态。你可以从乘法原理的角度再去体会当根节点是 1 时左子树为空。此时右子树有 n-1 个节点形态数是 dp[n-1]。如果 dp[0] 0那么根节点为 1 的所有情况都会被清零显然不对。所以这个初始值不是可选的它是递推成立的前提。4.3 记忆化 DFS另一种不过脑子的写法很多人在面试时紧张动态规划的表推着推着就乱了。我建议你掌握一种保底方案——记忆化搜索。它的核心是递归定义和递推公式完全一致只是用一个数组把已经算过的子问题缓存起来。def num_trees(n): memo {0: 1, 1: 1} def dfs(k): if k in memo: return memo[k] total 0 for i in range(k): total dfs(i) * dfs(k - i - 1) memo[k] total return total return dfs(n)这个写法的好处是不用明确推导出从 2 到 n 挨个填表的循环顺序只要递归关系正确、有记忆化复杂度同样是 O(n²)。缺点是递归深度可能达到 n如果 n 很大比如上万会爆栈但在本题范围内完全没问题。面试时如果一下子推不出迭代写法先写记忆化递归拿到分再优化成迭代也是实战中合理的策略。4.4 从这一题出发还能延伸出什么我做完这道题之后习惯性地看了一下相关变体如果要求输出所有 BST 的具体结构而不是只数数量就是95. 不同的二叉搜索树 II那时才真正需要递归构造树且不能用卡特兰数偷懒如果给定一个具体的 BST要求验证它是不是合法的二叉搜索树那就是中序遍历或递归区间约束的问题如果把节点总数固定改成树的深度不超过某个值或左右子树高度差受限计数递推就需要多一维状态。我特别建议你把95. 不同的二叉搜索树 II连着做掉。一道题考数有几个另一道题考具体长什么样两道题一起做你对递归拆分的理解会深很多。我自己当年是先做了 II 再回来做 I反而觉得 I 简单得不可思议因为递归构造的过程已经把枚举根节点、合并左右子树的思维焊死在脑子里了。还有一个实战小经验在面试中如果被问到这道题不要上来就背卡特兰数公式。面试官更想看到的是你从枚举根节点出发自然推导出 DP 递推式的过程。卡特兰数可以作为最后的一句总结但绝不是开场白。把递推关系讲清楚再提一句这个序列其实就是卡特兰数所以也可以用通项公式 O(n) 计算会让你的回答完整且有深度。