题目描述
这是 LeetCode 上的 「95. 不同的二叉搜索树 II」 ，难度为 「中等」。
Tag : 「树」、「二叉搜索树」、「BST」、「DFS」、「递归」、「爆搜」
给你一个整数 n，请你生成并返回所有由 n 个节点组成且节点值从 1 到 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：
代码语言：javascript复制输入：n = 1
输出：[[1]]
提示：
回溯算法
题目要我们求所有所能构造的二叉搜索树的具体方案，而给定 n个节点所能构成的二叉搜索树的个数为 卡特兰数。
其他方案数同为卡特兰数的还包括：凸多边形三角划分、n 对括号正确匹配数目 ...
回到本题，根据二叉搜索搜索的特性，若某个子树的根节点为 root，那么 root 的左子树任意节点值均比 root.val 要小，root 的右子树任意节点值均比 root.val 要大。
因此，假设我们使用 [l, r]连续段来构造二叉搜索树，并且选择了节点 t 作为二叉搜索树的根节点时，那么使用[l, t - 1] 构造出来的二叉搜索树均可作为根节点 t的左子树；同理，使用 [t 1, r]构造出来的二叉搜索树均可作为根节点 t 的右子树。
也就是说，我们可以设计递归函数 List<TreeNode> dfs(int l, int r)，含义为使用连续段 [l, r]进行二叉搜索树构造，并返回相应集合。
最终答案为 dfs(1, n)，起始我们可以枚举 [1, n]范围内的的每个数 t 作为根节点，并递归 dfs(l, t - 1) 和 dfs(t 1, r) 获取左右子树的集合 left 和 right，结合「乘法原理」，枚举任意左子树和任意右子树，即可得到 t 作为根节点的二叉搜索树方案集，枚举所有 t 后即可得到所有二叉搜索树的总集。
❝注意：当我们运用乘法原理，来构造以
t为根节点的二叉搜索树时，其left或right某一边可能为空集，但此时我们仍要将非空的一边子树进行挂载。为了确保两层新循环的逻辑会被执行，对于空集我们不能使用null来代指，而要使用[null]来代指。 ❞
Java 代码：
代码语言：javascript复制class Solution {
public List<TreeNode> generateTrees(int n) {
return dfs(1, n);
}
List<TreeNode> dfs(int l, int r) {
if (l > r) return new ArrayList<>(){{add(null);}};
List<TreeNode> ans = new ArrayList<>();
for (int i = l; i <= r; i ) {
for (TreeNode x : dfs(l, i - 1)) {
for (TreeNode y : dfs(i 1, r)) {
TreeNode root = new TreeNode(i);
root.left = x; root.right = y;
ans.add(root);
}
}
}
return ans;
}
}
TypeScript 代码：
代码语言：javascript复制function generateTrees(n: number): Array<TreeNode | null> {
function dfs(l: number, r: number): Array<TreeNode | null> {
if (l > r) return [null]
const ans = new Array<TreeNode>()
for (let i = l; i <= r; i ) {
for (const x of dfs(l, i - 1)) {
for (const y of dfs(i 1, r)) {
const root = new TreeNode(i)
root.left = x; root.right = y
ans.push(root)
}
}
}
return ans
}
return dfs(1, n)
}
Python 代码：
代码语言：javascript复制class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def dfs(l, r):
if l > r:
return [None]
ans = []
for i in range(l, r 1):
for x in dfs(l, i - 1):
for y in dfs(i 1, r):
root = TreeNode(i)
root.left, root.right = x, y
ans.append(root)
return ans
return dfs(1, n)
- 时间复杂度：卡特兰数
- 空间复杂度：卡特兰数
最后
这是我们「刷穿 LeetCode」系列文章的第 No.95 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
