题目描述
思路解析
一句话答案：LeetCode 95 不同的二叉搜索树 II 要构造所有形态而非计数:枚举每个值当根,左区间全部形态与右区间全部形态做笛卡尔积,空区间返回[null]才不漏,时间 O(n·Cₙ)。
先认几个词:节点、根、中序遍历都指什么
先认几个词:树由节点(装一个值的圆圈)连成,顶上那个是根,每个节点向下挂的左右两串是它的左子树、右子树;BST(二叉搜索树)要求任一节点左子树全比它小、右子树全比它大;中序遍历即按「左子树-根-右子树」走一遍整棵树,BST 这样走出来值正好从小到大;值域指取值范围,本题即 1 到 n。
给定 n,返回用 1 到 n 拼出的所有结构不同 BST,每棵都真的建出来。n=3 有 5 棵。它和只问个数的「不同的二叉搜索树」不同,要把结构逐棵摆出来。
为什么不能随手拼,棵数账先算清
随手把节点组装再逐棵验证,合法的树有多少、怎么不重不漏地生成控制不住。棵数本身就是卡特兰数(组合计数得出的一列数,记 Cₙ),n=3 是 5、n=8 已上千,增长接近 4ⁿ。
卡特兰数公式只能算出「有几棵」,给不出每棵长什么样,还得顺着 BST 性质把树拆出来。
BST 性质怎么把区间一分为二
把 BST 中序升序反过来用:选值 i 当根,比 i 小的 [l,i-1] 落左子树、比 i 大的 [i+1,r] 落右子树,一个值都不能跑错边。
原问题就切成两个同类小问题:左子树是 [l,i-1] 的所有 BST、右子树是 [i+1,r] 的,这种拆法叫分治。build(l,r) 表示区间 [l,r] 能拼出的所有 BST 根节点列表,返回一串树不是一个数。
左右为什么要两两组合、空区间返回 [null]
build(l,r) 让 l 到 r 每个值轮流当根 i。左边 build(l,i-1) 有若干形态、右边 build(i+1,r) 也有若干,任意左形态都能配任意右形态——这叫笛卡尔积。左 a 种、右 b 种,以 i 为根就有 a×b 棵;只取左右各一种会漏树。
空区间最容易写错。当 l 大于 r(如根取最小值时左边为空),build 必须返回只含 null 的 [null] 而非空列表 []。空子树也算一种形态,得在笛卡尔积里占位;若返回 [],外层配对一次都进不去,这个根的组合全丢。
拿 n=3 亲手把五棵拼出来
build(1,3),让 1、2、3 轮流当根。根取 1:左边空 [null] 一种,右边 build(2,3) 有「2 右挂 3」「3 左挂 2」共 2 种,1 乘 2 = 2 棵。根取 2:左右各是单节点 1 和 3,1 乘 1 = 1 棵。根取 3:左边 build(1,2) 2 种(1 右挂 2、2 左挂 1)、右边空 1 种,2 乘 1 = 2 棵。
三个根加起来 2+1+2 = 5 棵,和答案对上;每个根的棵数正好是左区间形态数乘右区间形态数,五棵中序都是 1、2、3。
复杂度多少,空区间和 n=1 两个边界别弄错
产出的棵数就是卡特兰数 Cₙ,每棵约 n 个节点要新建,时间空间都被棵数主导,O(n·Cₙ) 量级,n 最大到 8。
两个边界最容易写错。一是空区间必须返回 [null] 而非 [],这是分治能组合的根基,返回 [] 整根组合全丢。二是 n=1:区间 [1,1] 只单节点一棵。左右子区间按根切成 [l,i-1] 和 [i+1,r],差一个值 BST 性质就破。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「每个值轮流当根 → 左区间全部形态 × 右区间全部形态」,下面对 n=3 逐棵套它。
BST 性质：先看一棵具体的 BST 找感觉:根 2、左 1、右 3。BST 要求左子树都比根小、右子树都比根大,等价于中序遍历严格升序 1、2、3。下面要找的,就是 n=3 时所有满足这一点的不同结构。
总览 · 枚举根：先纵览思路:1、2、3 三个值都可以当根。每选定一个根,左右两个子区间就定下来了,各自再递归。下面从根=1 开始一棵棵拼。
根=1 · 定区间：第一步选 1 当根。1 是最小值,左边没有更小的,所以左子树为空;右边要装下 [2,3],得先列出这个区间的所有 BST 形态。
右区间[2,3] · 形态1：区间 [2,3] 的第一种形态:让 2 当根。3 比 2 大,只能当 2 的右孩子,得到一条向右的小斜链 2→3。
根=1 · 组合①：把刚才的右子树 2→3 接到根 1 的右边(紫色是新接上的部分)。左边为空、右边这一种形态,组合出一棵完整的树。
第 1 棵完成：第 1 棵成形:1 的右边是 2、2 的右边是 3。验证一下中序遍历正好是 1、2、3 升序,是合法 BST。已生成 1 棵。
右区间[2,3] · 形态2：区间 [2,3] 还有第二种形态:让 3 当根。2 比 3 小,当 3 的左孩子,得到 3、左挂 2。
根=1 · 组合②：把第二种右子树(3、左挂 2)接到根 1 右边。这就是以 1 为根的第二棵。
第 2 棵完成：第 2 棵成形。以 1 为根的树到此有 2 棵——正是右区间 [2,3] 的两种形态各配一棵。已生成 2 棵。
根=2 · 定区间：换 2 当根。左边只剩 [1]、右边只剩 [3],都是单个值,各自只有一种形态(就是它自己)。所以以 2 为根只能拼出 1 棵。
根=2 · 组合：把单节点 1 接到 2 的左边、单节点 3 接到右边(紫色)。左右各一种,组合出唯一一棵。
第 3 棵完成：第 3 棵成形:2 当根,左右各挂一个,最平衡。中序仍是 1、2、3。已生成 3 棵。
根=3 · 定区间：最后让 3 当根。3 是最大值,右边为空;左边要装 [1,2],和刚才的 [2,3] 一样,这个区间也有两种形态。
左区间[1,2] · 形态1：区间 [1,2] 的第一种形态:1 当根,2 比 1 大、挂它右边,得到 1→2。
根=3 · 组合①：把左子树(1、右挂 2)接到根 3 的左边。右边为空,组合出一棵。
第 4 棵完成：第 4 棵成形:3 当根、左边是 1、1 的右边是 2。中序还是 1、2、3。已生成 4 棵。
左区间[1,2] · 形态2：区间 [1,2] 的第二种形态:2 当根,1 比 2 小、挂左边,得到 2、左挂 1。
根=3 · 组合②：把第二种左子树(2、左挂 1)接到根 3 左边。这是以 3 为根的第二棵。
第 5 棵完成：第 5 棵成形:3、左 2、再左 1,一路向左斜。以 3 为根同样 2 棵。已生成 5 棵,全部集齐。
全部完成 · 计数：五棵集齐。按根拆开看:以 1 为根 2 棵、以 2 为根 1 棵、以 3 为根 2 棵,2+1+2=5,正好是卡特兰数 C₃。每棵的「棵数」都等于「左区间形态数 × 右区间形态数」,这就是笛卡尔积的威力。
边界:n=1 一棵;空区间返回 [null] 是分治能正确组合的根基。
面试重点:对比 lc96 只数个数;以及用记忆化缓存区间结果。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self,val=0,left=None,right=None): self.val=val; self.left=left; self.right=rightclass Solution: def generateTrees(self, n: int) -> List[Optional[TreeNode]]: from functools import lru_cache @lru_cache(None) def build(l,r): if l>r: return (None,) ans=[] for x in range(l,r+1): for a in build(l,x-1): for b in build(x+1,r): ans.append(TreeNode(x,a,b)) return tuple(ans) return list(build(1,n))复杂度
- 时间：O(n · Cₙ)，结果共有 Cₙ(第 n 个卡特兰数)棵树,每棵约 n 个节点要新建;Cₙ ≈ 4ⁿ / (n^1.5 · √π),增长很快
- 空间：O(n · Cₙ)，要把所有树都存下来返回;不计输出本身时,递归栈与中间列表为多项式级
易错点
面试追问把动画讲成自己的话
追问这题和「不同的二叉搜索树」(只求个数)是什么关系?
追问能不能加记忆化加速?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树的层序遍历 II
LeetCode 107 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题