§1

题目描述

用 1 到 n 这 n 个数当节点，问能组成多少种结构不同的二叉搜索树（BST）。

输入 n = 3

输出 = 5

§2

思路解析动画文字版

先看其中一棵：根选 2：先画根选 2 这棵：1 在左、3 在右，左右各一个点。根选 1 的、根选 3 的还有好几棵——不逐棵画，后面用 DP 直接把总数 5 数出来。

想真的把每棵树都摆出来再数，数量随 n 暴涨，n 大一点就画不动了。题目只问数量，我们不该去构造，要去算。

关键观察：BST 里数值是有序的。一旦定下谁当根，比它小的全在左子树、比它大的全在右子树，左右各有几个点就被锁死了。

灵魂帧 · 选 i 当根，左右点数被锁死：把 1、2、3 摆成一排。手指点在 2 上当根，它左边天然只剩 1 个数、右边只剩 1 个数——位置一选，左右的「点数」立刻确定，跟具体是哪个数无关。

灵魂帧 · 同一排，换 1 当根：手指挪到最左的 1。它左边一个数都没有（0 个点），右边剩 2 个点。于是问题变成：左边 0 个点能搭几棵 × 右边 2 个点能搭几棵。这就把大问题拆成了两个更小的同类问题。

再关键一步：3 个连续数和 30、31、32 这三个数，搭出的 BST 形状数完全一样——只跟「点的个数」有关。所以定义 dp[k] 等于 k 个点能搭多少棵 BST，左右子树都能直接复用它。

地基 · dp[0] 和 dp[1]：dp[0] 必须等于 1。空子树不是「没有」，它是一种合法形态——当某个根没有左孩子时，左边那一半就贡献「1 种」。这一格写错，整张表全塌。dp[1] 自然是 1。

算 dp[2] · 枚举两个根：2 个点。第一个数当根：左 0 个右 1 个，dp[0]×dp[1]=1。第二个数当根：左 1 个右 0 个，dp[1]×dp[0]=1。两种根各一种树，加起来 dp[2]=2。注意是「左 × 右」相乘，再把每个根的结果「相加」。

算 dp[3] · 根=最小的那个：3 个点，先让最小的数当根。它左边 0 个点（dp[0]=1）、右边 2 个点（dp[2]=2），相乘得 2 种。这一项还没写进 dp[3]，先记着。

算 dp[3] · 根=中间那个：换中间的数当根，左右各 1 个点，dp[1]×dp[1]=1 种。注意右边那 1 个点和左边那 1 个点，搭出的形状数都是 dp[1]，跟具体数值无关——这正是只看个数的好处。

算 dp[3] · 根=最大的，求和落格：最后让最大的数当根，左 2 个右 0 个，dp[2]×dp[0]=2。把三个根的结果加起来：2+1+2=5，写进 dp[3]。这就是样例 n=3 的答案 5。

顺势填 dp[4]、dp[5]：dp[4] 枚举 4 个根，每个根的左右点数加起来都是 3，凑出 14。dp[5] 同理得 42。每个新格只用到左边已经填好的格，所以从小到大一路填下去就行。1、1、2、5、14、42 这串数，就是著名的卡特兰数。

一句话本质：固定一个根，左右两半互不干扰，方案数相乘；换不同的根方案数相加。这就是计数 DP 的母题套路。

雷区实演 · 别按「排列数」去数：常见错觉：以为答案是 1、2、3 的排列数 3 的阶乘等于 6。错在哪？排列数数的是「插入顺序」、BST 数的是「形状」——比如 2、1、3 和 2、3、1 两种顺序长出的是同一棵树（根 2、左 1、右 3），多种顺序会塌成同一形状。两者没有简单加减关系：n=3 碰巧是 6 与 5，到 n=4 就是排列 24、形状只有 14，差距迅速拉大。千万别用排列数去估形状数。

边界三连：三个边界：n=0 看地基对不对，n=1 看最小规模，n=19 专门压测大数会不会溢出。

面试追问：三个高频追问：卡特兰公式、升级成构造题 LC95、以及为什么能只看个数。

迁移阶梯：学会这招后去迁移：LC95 把计数换成构造、矩阵链乘 / 戳气球（LC312）也是枚举「最后处理谁」再把区间一拆两半。点开 DP 专题或问问 AI 助教「还有哪些题是枚举分割点」，连成一串。

§3

参考代码

class Solution:    def numTrees(self, n: int) -> int:        dp = [0] * (n + 1)        dp[0] = 1            # 空树算一种        for nodes in range(1, n + 1):            for root in range(1, nodes + 1):                left = root - 1          # 左子树点数                right = nodes - root     # 右子树点数                dp[nodes] += dp[left] * dp[right]        return dp[n]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(n²)，外层 n 个规模，内层每个规模最多枚举 n 个根
空间复杂度：O(n)，只存一维 dp 数组

§5

可套用的代码模板

把「根」抽象成「分割点」：左半 split 个、右半 size-1-split 个，相乘累加。判据——只要问题能「定一个中心点，左右两半独立计数」，就往这个骨架上套。

# 计数型区间 DP 通用骨架dp = [0] * (n + 1)dp[0] = 1                       # 空区间 = 1 种基底for size in range(1, n + 1):    # 枚举区间长度    for split in range(size):   # 枚举谁当分割点/根        left = split            # 左半点数        right = size - 1 - split  # 右半点数（扣掉分割点）        dp[size] += dp[left] * dp[right]return dp[n]

§6

易错点

✗ 错误写法：dp[0] 忘了设成 1

✓ 正确写法：空树必须算一种方案

根在最左或最右时，有一侧是空子树，乘上 dp[0]。dp[0]=0 会把整项乘成 0，答案全错

✗ 错误写法：左右点数写成 root 和 nodes-root

✓ 正确写法：应是 root-1 和 nodes-root

根节点自己要从点数里扣掉，左边是 root-1 个、右边才是 nodes-root 个

✗ 错误写法：大 n 用 int 存 dp

✓ 正确写法：C++/Java 用 long

卡特兰数增长很快，n=19 就接近 int 上限，会悄悄溢出成负数

面试追问把动画讲成自己的话

追问这串数是卡特兰数吗？有没有公式 O(n) 算？

是。卡特兰数有递推式 C(n) = C(n-1)·(4n-2)/(n+1)，一遍循环 O(n) 就能算出，比 O(n²) DP 更快。面试讲清 DP 推导即可，能补一句公式更亮眼。

追问如果不只要数量，还要真把每棵树构造出来呢？

那就是 LC95「不同的二叉搜索树 II」。把「点数相乘」换成「真的递归生成左右子树列表，再两两拼接挂到根上」，思路同源、实现升级。

追问为什么左右子树能直接复用 dp，不用管具体是哪几个数？

BST 的形状只取决于节点的相对大小关系，跟具体数值无关。k 个连续数和任意 k 个不同数，搭出的形状种类完全一样，所以统一记成 dp[k]。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 # 空树算一种 for nodes in range(1, n + 1): for root in range(1, nodes + 1): left = root - 1 # 左子树点数 right = nodes - root # 右子树点数 dp[nodes] += dp[left] * dp[right] return dp[n]

# 计数型区间 DP 通用骨架dp = [0] * (n + 1)dp[0] = 1 # 空区间 = 1 种基底for size in range(1, n + 1): # 枚举区间长度 for split in range(size): # 枚举谁当分割点/根 left = split # 左半点数 right = size - 1 - split # 右半点数（扣掉分割点） dp[size] += dp[left] * dp[right]return dp[n]