教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解以《算法通关手册》中的 0095. 不同的二叉搜索树 II 文档为主体围绕「给定 1 到 n 的节点值枚举生成所有结构合法的二叉搜索树BST」这一核心问题展开。通过本文你将掌握如何利用二叉搜索树的递归性质将整树问题划分为左右子树子问题、如何用「笛卡尔积」方式组合所有合法形态以及为什么本题的结果数量和解空间复杂度与卡特兰数直接相关。文中代码可直接复制运行并附带边界处理、复杂度推导与同仓库姊妹题0096的对照分析。一、题目概览从「计数」到「枚举」的升级项目内容题目编号0095. 不同的二叉搜索树 IIUnique Binary Search Trees II标签树、二叉搜索树、动态规划、回溯、二叉树难度中等题目链接0095. 不同的二叉搜索树 II - 力扣问题描述给定一个整数 $n$请生成并返回以 $1$ 到 $n$ 为节点值构成的所有「二叉搜索树」可以按任意顺序返回答案。说明约束$1 \le n \le 8$。由于结果数量随 $n$ 呈卡特兰数级增长$n 8$ 时已有 1430 棵题目刻意将 $n$ 限制在很小的范围内保证枚举全部结构在时间和空间上可行。示例 1输入n 3 输出[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]示例 2输入n 1 输出[[1]]输出格式为 LeetCode 通用的二叉树层序遍历序列化表示按层自上而下、从左到右列出节点值空节点用null标记。例如[2,1,3]表示根节点值为 2、左孩子为 1、右孩子为 3 的一棵 BST而[1,null,2,null,3]表示根为 1、右孩子为 2、2 的右孩子为 3 的一棵右斜树。示例 1 输出的 5 棵 BST恰好就是 $n 3$ 时所有合法的二叉搜索树形态。值得注意的是本题与 0096. 不同的二叉搜索树 互为姊妹题0096 只要求输出「数量」一个整数而 0095 要求输出「全部树结构」本身是枚举类问题的代表。二、前置知识二叉搜索树的结构性质与链式存储要枚举 BST首先必须明确 BST 的定义。在《算法通关手册》的 05_04 二叉搜索树 一节中BST 被定义为满足以下性质的二叉树任意节点的左子树非空时左子树所有节点的值均小于该节点的值任意节点的右子树非空时右子树所有节点的值均大于该节点的值任意节点的左右子树本身也都是二叉搜索树递归定义空树也视为二叉搜索树。由此得到 BST 最核心的特性左子树所有节点值 根节点值 右子树所有节点值且对 BST 做中序遍历得到的节点值序列一定是严格递增的。更关键的是上述定义本身就是递归的——树的合法性与子树合法性是相互蕴含的关系这正是我们可以用递归来枚举 BST 的理论基础。在代码实现上题目需要返回树结构因此采用链式存储结构表示二叉树。仓库基础文档 05_01 树基础 中给出的标准节点定义如下class TreeNode: 二叉树节点定义链式存储结构 属性: val: 节点存储的值 left: 指向左子节点的指针无左子节点时为 None right: 指向右子节点的指针无右子节点时为 None def __init__(self, val0, leftNone, rightNone): self.val val # 节点的值 self.left left # 左子节点指针 self.right right # 右子节点指针本题后续所有代码均基于该节点结构。三、核心思路以根节点为分界点的递归分治3.1 关键观察选定根后左右子树是互不重叠的独立子问题由于 1 到 $n$ 是连续的整数序列且 BST 要求「左 根 右」因此根节点的取值直接决定了左右子树的取值集合如果根节点值为 $i$那么左子树只能由 $(1, 2, ..., i - 1)$ 共 $i - 1$ 个节点构成右子树只能由 $(i 1, i 2, ..., n)$ 共 $n - i$ 个节点构成左右子树互不重叠且各自都必须是合法的 BST。这意味着「用 $[start, ..., end]$ 构造所有 BST」这个原问题在选定根 $i$ 之后被拆分成了两个结构完全相同、但规模更小的子问题「用 $[start, ..., i-1]$ 构造所有左 BST」和「用 $[i1, ..., end]$ 构造所有右 BST」。子问题与原问题同构天然适合递归求解。3.2 算法步骤对应原文档「思路 1递归遍历」定义递归函数generateTrees(start, end)表示生成由 $[start, ..., end]$ 区间内所有节点构成的全部合法二叉搜索树返回根节点列表。具体步骤如下递归终止条件如果start end说明区间为空、无可选节点此时子树为空树返回[None]注意返回的是包含一个None的列表而非空列表这样上层才能对「空树」也做组合。初始化结果数组trees []用于存放当前区间所有可能的 BST 根节点。枚举根节点遍历 $[start, ..., end]$ 中的每一个节点值 $i$将其作为根节点。递归构建左子树列表left_trees generateTrees(start, i - 1)递归构建右子树列表right_trees generateTrees(i 1, end)。组合左右子树对left_trees与right_trees做笛卡尔积——每一个左子树都可以与每一个右子树搭配构造一棵以 $i$ 为根的树并将结果加入trees。返回结果返回trees。第 4 步的「笛卡尔积」是本题的精髓固定根 $i$ 后任意一棵合法左子树与任意一棵合法右子树组合出的树都必然合法因为左右子树各自的取值范围天然满足 BST 的大小关系因此左子树集合与右子树集合可以自由配对种数为 $|left_trees| \times |right_trees|$。四、完整代码与逐行解析在原文档给出的代码基础上补充节点结构与详细注释得到可直接运行的完整实现from typing import List, Optional class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def generateTrees(self, n: int) - List[Optional[TreeNode]]: # 边界处理n 0 时没有任何节点也无法构成任何树返回空列表 if n 0: return [] def generateTrees(start: int, end: int) - List[Optional[TreeNode]]: # 递归终止条件区间为空返回 [None]表示“只有空树这一种选择” if start end: return [None] trees [] # 存放 [start, end] 区间能构成的所有 BST 根节点 for i in range(start, end 1): # 枚举根节点值 i # 左子树由 [start, i - 1] 构成 left_trees generateTrees(start, i - 1) # 右子树由 [i 1, end] 构成 right_trees generateTrees(i 1, end) # 笛卡尔积每个左子树 × 每个右子树 for left_tree in left_trees: for right_tree in right_trees: curr_tree TreeNode(i) # 新建根节点 curr_tree.left left_tree curr_tree.right right_tree trees.append(curr_tree) # 收集一棵完整 BST return trees return generateTrees(1, n)逐行要点说明if n 0: return []题目约束 $1 \le n \le 8$ 本不会触发但保留该分支可以保证函数对任意输入都语义正确0 个节点构不成任何非空树也不该返回「一棵空树」。return [None]终止条件返回[None]而非[]是本题最容易写错的地方。若返回空列表上层循环for left_tree in left_trees将不会执行任何一次导致所有以叶子节点为根的组合全部丢失。for i in range(start, end 1)根节点可以是区间内任意一个值每个取值对应一类完全不同的树形态。TreeNode(i)每次新建一个根节点而左右子树直接引用递归返回的节点指针共享复用这一细节直接决定了空间复杂度详见第六节。五、示例推演n 3 的完整递归过程以 $n 3$ 为例generateTrees(1, 3)的执行过程如下根 1左子树generateTrees(1, 0)返回[None]右子树generateTrees(2, 3)有 2 种形态以 2 为根、右孩子 3以 3 为根、左孩子 2。组合出 2 棵1 → 2 → 3右斜树1 → 33 的左孩子为 2根 2左子树generateTrees(1, 1)返回[1]右子树generateTrees(3, 3)返回[3]。组合出 1 棵2的左孩子1、右孩子3完全平衡形态根 3左子树generateTrees(1, 2)有 2 种形态对称于第 1 步右子树返回[None]。组合出 2 棵3 → 1 → 2左斜树3 → 11 的右孩子为 2合计 $2 1 2 5$ 棵与示例输出完全一致。可以观察到递归的「递推」阶段不断把区间一分为二地拆小直到区间为空「回归」阶段则把子问题的解两两组合向上合并出完整的树——这与《算法通关手册》07_02 递归算法 一节总结的「递推 回归」模型完全对应是「分治型递归」的典型范例。六、复杂度分析卡特兰数决定解空间规模原文档给出的复杂度结论为时间复杂度$O(C_n)$其中 $C_n$ 是第 $n$ 个卡特兰数。空间复杂度$O(C_n)$其中 $C_n$ 是第 $n$ 个卡特兰数。卡特兰数的定义为 $C_n \dfrac{1}{n1}\dbinom{2n}{n}$其前几项为 $1, 1, 2, 5, 14, 42, 132, 429, 1430, \dots$恰好与「$n$ 个节点能构成的 BST 数量」一一对应。这一对应关系并非巧合将根节点 $i$ 固定后左子树有 $C_{i-1}$ 种、右子树有 $C_{n-i}$ 种总数量满足卷积递推$$C_n \sum_{i1}^{n} C_{i-1} \times C_{n-i}$$这正是卡特兰数的标准递推式也是 0096. 不同的二叉搜索树 中动态规划解法的数学本质该题定义 $dp[i]$ 为 $i$ 个节点可构成的 BST 个数转移方程为 $dp[i] \sum_{1 \le j \le i} \lbrace dp[j-1] \times dp[i-j] \rbrace$$dp[0] 1$。理解本题复杂度的关键还在于子树的共享复用如第四节的代码所示每个组合只新建一个根节点TreeNode(i)左右子树直接引用递归返回的指针并不会把整棵子树逐节点复制一遍。因此总的新建节点数 结果树的数量 $C_n$每个结果恰好对应一次根节点新建每个根节点完成两次指针赋值后即可返回摊还到每棵树上为常数级工作加上递归调用的开销总时间与 $C_n$ 同阶即 $O(C_n)$。空间上需要保存全部 $C_n$ 个根节点引用结果本身递归调用栈深度最多为 $n$因此总空间为 $O(C_n)$。也正是因为 $C_n$ 随 $n$ 指数级膨胀题目约束 $n \le 8$$C_8 1430$才保证了算法在时空上均可接受。七、边界情况与易错点终止条件必须返回[None]而不是[]空区间代表「空树」这一种合法选择只有返回单元素列表上层组合循环才能执行否则所有叶子节点上的组合都会被吞掉。空输入的特殊处理n 0时应返回[]没有任何树与generateTrees(1, 0)返回[None]一棵空树语义不同二者不可混用。虽然本题约束 $n \ge 1$但该分支能增强代码的健壮性。左右子树不可交换BST 是有序树05_01 一节明确「二叉树的左右子树顺序不可交换」固定根 $i$ 后值小的区间只能放左边、值大的区间只能放右边不能交叉放置否则将破坏 BST 性质或产生重复形态。结果顺序不影响正确性题目允许按任意顺序返回答案因此递归中按i从小到大枚举即可无需额外排序去重——不同根节点、不同左右子树组合天然产生不同的树。八、在仓库中的定位与延伸阅读本题在《算法通关手册》中被归入「树 / 二叉搜索树」与「递归 / 分治」交叉分类。仓库的 00_06 题目分类列表 将其收录于递归算法题目清单中标签同时包含动态规划与回溯说明本题是多算法视角交叉的经典题。建议按以下顺序延伸阅读姊妹题对照0096. 不同的二叉搜索树 —— 同一问题的「计数版」用动态规划推导出卡特兰数递推可与本文的枚举版互为印证理解「计数」与「枚举」在思路与复杂度上的差异。数据结构基础05_01 树基础 —— 树的定义、二叉树性质、链式存储结构含TreeNode标准定义。BST 专项05_04 二叉搜索树 —— BST 的查找、插入实现进一步体会「左 根 右」性质在算法中的应用。算法思想07_02 递归算法 —— 递归三步法写递推公式、确定终止条件、翻译为代码与递推/回归过程分析是理解本节解法的理论支撑。同类树题仓库中还收录了 0098. 验证二叉搜索树判断给定树是否合法 BST与 0094. 二叉树的中序遍历BST 中序遍历递增性质的应用可与本题的「构造」形成「验证 — 遍历 — 构造」的完整闭环。最后提醒本题因解空间为卡特兰数级仅适合在 $n$ 较小≤ 8的场景下枚举若只需数量、无需具体结构应优先采用 0096 的 $O(n^2)$ 动态规划做法避免不必要的指数级枚举开销。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐95. 不同的二叉搜索树 II 题解从分治递归生成到卡特兰数复杂度剖析95. 不同的二叉搜索树 II 题解从分治递归生成到卡特兰数复杂度剖析 本篇题解以 leetcode 仓库中 problems/95.unique binar文档教程知识库LeetCode 96. 不同的二叉搜索树分治 × 笛卡尔积 × 记忆化递归的 BST 计数解法LeetCode 96. 不同的二叉搜索树分治 × 笛卡尔积 × 记忆化递归的 BST 计数解法 本篇文章围绕 LeetCode 96「不同的二叉搜索树Un文档教程知识库TalkGo 算法之美有序数组转二叉搜索树与不同的二叉搜索树 II——树的构造专题实战TalkGo 算法之美有序数组转二叉搜索树与不同的二叉搜索树 II——树的构造专题实战 本文基于 TalkGoGo 夜读开源社区 content/algo文档教程上一篇Apache Pulsar Topic Compaction 原理与实战基于键的日志压缩机制完整指南下一篇DDrawCompat终极指南如何让经典游戏在现代Windows系统上完美运行的完整解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考