题目描述
思路解析动画文字版
记住「每个值轮流当根 → 左区间全部形态 × 右区间全部形态」,下面对 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题