95. 不同的二叉搜索树 II

题意

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不

同 二叉搜索树 。可以按 任意顺序 返回答案。

难度

中等

示例

示例 1：

095.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91II-20231030163552.png

输入：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]]

分析

首先我们来了解一下什么是二叉搜索树。

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

1. 空树是二叉搜索树。

2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点

的值。

3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点

的值。

4. 二叉搜索树的左右子树均为二叉搜索树。

——引自[二叉搜索树 & 平衡树 - OI

Wiki](https://oiwiki.org/ds/bst/)

简单来说，二叉搜索树需要满足：每个节点的左子树都比自己小、右子树都比自己大。

最简单的情况，一条有序的链表，就算是一个二叉搜索树。例如：

095.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91II-20231030164012.png

好，接下来我们要知道节点个数为 n 的二叉搜索树的个数是多少。

假设 n 个节点的 二叉搜索树 的个数为$ G(n) ， f(i) 为 以 i $作为根节点的 n 个节点的二叉

搜索树个数。

我们可以得到这样的式子：

$ G(n) = f(1) + f(2) + + f(n) $

并且当我们分析$ f(i) $的时候，还可以得到这样子一个式子：

$ f(i) = G(i-1) * G(n - i) $

因为我们知道总数为 n 的话，当前节点的两个子树，必然是大小为 i-1 和 n-i 的两棵二叉

搜索树。

综合一下两个公式我们能得到如下式子：

$ G(n) = G(0) * G(n - 1) + G(1) * G(n - 2) + + G(n - 1) * G(0) $

而这，其实就是卡特兰数。

简单来说，卡特兰数就是在某些特定限制条件下，可能的组合或排列的数量。

举一个常见的例子：你有一堆左括号和右括号，要组成一个正确的括号组合（即每个左括

号都有一个与之对应的右括号），那么可能的组合数就是一个卡特兰数。

好，我们选择一个数作为根节点，然后分配左右子树，最后按照左右子树的大小继续递归

建树即可得到答案。

/**

* Definition for a binary tree node.

 * public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

*}

*/

class Solution {

// 主方法，接收一个整数 n 作为参数

public List<TreeNode> generateTrees(int n) {

// 当 n 为 0 时，没有可生成的树，直接返回一个空的列表

if (n == 0) {

return new LinkedList<TreeNode>();

}

// 调用辅助方法 generateTrees，生成从 1 到 n 的所有可能的二叉搜索树

return generateTrees(1, n);

}

// 辅助方法，接收两个整数作为参数，表示生成树的值的范围

public List<TreeNode> generateTrees(int start, int end) {

List<TreeNode> trees = new LinkedList<TreeNode>(); // 用于存储生成的所有

树的列表

// 当开始值大于结束值时，表示该区间无有效数字，返回一个包含 null 的列表

if (start > end) {

trees.add(null);

return trees;

}

// 遍历从 start 到 end 的所有数字，将每一个数字作为根节点

for (int i = start; i <= end; i++) {

// 生成所有可能的左子树

List<TreeNode> leftTrees = generateTrees(start, i - 1);

// 生成所有可能的右子树

List<TreeNode> rightTrees = generateTrees(i + 1, end);

// 对于每一颗左子树和右子树的组合，创建一个新的树

for (TreeNode left : leftTrees) {

for (TreeNode right : rightTrees) {

TreeNode newTree = new TreeNode(i); // 创建一个新的树的根节点

newTree.left = left; // 将当前左子树连接到新树的左侧

newTree.right = right; // 将当前右子树连接到新树的右侧

 trees.add(newTree); // 将新生成的树添加到 trees 列表中

}

}

}

return trees; // 返回生成的所有树的列表

}

}

当输入 n = 3 时，我们需要构造所有可能的二叉搜索树，其中树的节点值从 1 到 3。

遍历每个数字 i 从 1 到 3，将其视为根节点，并递归地为其左右子树生成所有可能的结

构。

让我们模拟题解的过程：

1. i = 1 作为根节点：

– 左子树: 无

– 右子树: 2,3

• 当 2 作为根节点：左子树无，右子树有 3

• 当 3 作为根节点：左子树有 2，右子树无

结果：

1 1

2 3

/

3 2

2. i = 2 作为根节点：

– 左子树: 1

– 右子树: 3

结果：

2

/

1 3

3. i = 3 作为根节点：

– 左子树: 1,2

• 当 1 作为根节点：右子树有 2，左子树无

• 当 2 作为根节点：左子树有 1，右子树无

– 右子树: 无

结果：

3 3

/ /

1 2

/

2 1

合并上述所有的结果，我们可以得到 5 个不同的二叉搜索树。

来看一下题解效率：

095.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91II-20231030171013.png

这题的核心思想是采用递归的方法来生成所有可能的二叉搜索树。

1. 递归基础:

当给定的范围内没有数字时（即 start > end），这意味着此处的子树为 null，所以

我们应该返回一个列表，其中只包含一个 null 元素。

2. 中间节点选择:

对于范围内的每个数字 i，我们都尝试将其作为当前树的根节点。也就是说，我们认

为每个数字都有可能作为根节点。

3. 左、右子树的生成:

– 对于根节点 i，它的左子树应该由 start 到 i - 1 的所有可能树组成，而右子树

应该由 i + 1 到 end 的所有可能树组成。

– 使用递归，我们可以得到两个列表：leftTrees 和 rightTrees，分别代表所有

可能的左和右子树。

– 然后，我们组合这些左子树和右子树，形成所有可能的树结构。

总结

本题通过总结公式从而得出构建二叉树的方法，这个套路其实也比较普遍，因为它和卡特

兰数有关，建议在刷题之余，有意识地去总结对应类别的题目，往往可以给我们带来意想

不到的收获。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees-ii/