LeetCode 95. 不同的二叉搜索树 II

2026-01-15 HGNULB 约 11 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 95. 不同的二叉搜索树 II

题意分析

给定整数 n，要求把 1 到 n 这 n 个互不相同的值组织成所有结构互不相同的二叉搜索树，并把每棵树的根节点都返回。注意返回的是树本身而不是数量——96 题只要个数，本题要把每一棵都真的建出来，这决定了时间复杂度下界必然与方案数同阶，没有任何「只算不建」的捷径。

二叉搜索树的性质是全题的钥匙：任取一个值当根，所有比它小的值必须全部落在左子树，所有比它大的值必须全部落在右子树，没有第三种可能。这把「n 个数怎么排」这种自由度极高的问题，牢牢约束成「选一个根，剩下的自动分成两段连续区间」。

约束里 n 只到 8。这个极小的上界本身就是信号：答案数量是卡特兰数，$n = 8$ 时是 1430 棵树，节点总数上万，规模可控但增长极快，说明出题人预期的是一个把所有方案穷举构造出来的解法，而不是某种多项式算法。

边界上要注意两点：n 至少为 1，所以不会出现「整棵树为空」的输入，但递归内部一定会遇到空区间，空区间必须返回一个「含有一个 null 的列表」而不是空列表，否则上层的笛卡尔积会整体塌成空；另外题目允许按任意顺序返回答案，不需要排序。

解法：递归枚举 + 记忆化

核心思路

暴力做法是生成 1 到 n 的全排列，对每个排列按顺序插入一棵二叉搜索树，再去重。这既慢（$n!$ 个排列）又要额外实现树的同构判断，而且不同排列可能生成同一棵树，去重逻辑本身就很麻烦。

瓶颈在于我们绕了远路：从排列出发，形状是插入过程的副产品，只能事后判重。换个方向，直接从形状出发——枚举谁当根。一旦确定根是 root，由二叉搜索树的性质，左子树只能由 $[l, root-1]$ 这段值构成，右子树只能由 $[root+1, r]$ 构成，两边互不干扰。于是任意一棵左子树配任意一棵右子树都是合法的、且互不相同的树，总数是两边方案数的乘积。

由此定义递归函数：build(l, r) 返回用连续区间 $[l, r]$ 中的所有值恰好构成的全部二叉搜索树的根节点列表。这个定义有两个要点：一是参数是区间而非集合，因为二叉搜索树的子树取值范围永远是连续的一段；二是返回的是列表而非单棵树，因为要穷举所有形状。

递归的组合方式就是笛卡尔积：对每个 root 从 l 枚举到 r，取 left = build(l, root-1)、right = build(root+1, r)，然后对每一对 (a, b) 新建一个值为 root 的节点，左右分别挂上 a 和 b。终止条件是 l > r，代表空区间，返回 [null]——注意是「装着一个空指针的列表」，语义是「空区间恰好有一种构成方式，就是空树」。如果返回空列表，笛卡尔积的循环一次都不会执行，整层结果就全没了。

最后是记忆化。观察 build(1, 3) 的展开过程会发现 build(2, 2)、build(1, 1) 这样的小区间会在不同的根选择下被反复求解。由于函数的返回值只由 (l, r) 决定，可以用一个以区间为键的表把结果缓存起来，第二次遇到同一个区间直接复用。这里复用的是同一批子树节点对象——不同的父节点会共享同一棵子树实例，判题只检查结构，因此完全合法；即使不加记忆化，经典写法里内层双重循环也早已在多个父节点间共享同一份左右子树了。

解题步骤

在入口处理 n == 0。虽然本题约束保证 n ≥ 1，但函数签名允许 0，此时应返回空列表而不是 [null]——外层要的是「树的列表」，一棵都没有和「有一棵空树」在判题上是两回事。

主逻辑交给 build(1, n)。用整个值域作为初始区间，把问题一次性交给递归定义。

进入 build 先查记忆表。键是区间的两个端点（Java 里拼成字符串，Go 里直接用 [2]int 数组当键），命中就直接返回缓存列表，省掉整棵子问题的重建。

判断 l > r 返回 [null] 并写入缓存。这是递归的基例，也是最容易写错的一行；把它也缓存起来是为了让所有空区间共享同一个列表对象，减少分配。

枚举 root 从 l 到 r。每个值都有资格当根，且不同的根一定给出不同的树（根的值不同，结构就不同），因此枚举天然不重不漏。

递归求出左右子树列表，再做双重循环组合。外层遍历左子树列表、内层遍历右子树列表，每一对组合都必须新建一个根节点，因为同一个 root 值会出现在多棵树里，复用同一个节点对象会让后来的赋值覆盖先前的左右指针。

组合结果全部收进 res，循环结束后写入缓存并返回。返回给上层的就是这个区间的全部方案，上层再把它当作某个更大区间的左子树或右子树候选。

以 n = 3 走一遍：调用 build(1, 3)。root = 1 时，左边是 build(1, 0)，空区间返回 [null]；右边是 build(2, 3)，它内部又枚举：root = 2 时左 build(2, 1) = [null]、右 build(3, 3)（其内部 root = 3，左右都是空区间，返回单节点 3），组合出 2 → 右 3；root = 3 时左 build(2, 2) 返回单节点 2、右 build(4, 3) = [null]，组合出 3 → 左 2。所以 build(2, 3) 给出两棵树，build(1, 3) 在 root = 1 下也就得到两棵：1 → 右(2 → 右3) 与 1 → 右(3 → 左2)。root = 2 时，左 build(1, 1) 返回单节点 1、右 build(3, 3) 命中缓存直接返回之前建好的单节点 3，组合出唯一一棵 2(左1, 右3)。root = 3 时，左 build(1, 2)：其中 root = 1 配右子 build(2, 2)（命中缓存）得到 1 → 右2，root = 2 配左子 build(1, 1)（同样命中缓存）得到 2 → 左1，共两棵；右边 build(4, 3) = [null]，于是得到 3 → 左(1 → 右2) 与 3 → 左(2 → 左1)。合计 2 + 1 + 2 = 5 棵，正是卡特兰数 $C_3 = 5$。

代码实现

// build(l, r) 返回区间内所有 BST。
class Solution {
    private final Map<String, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return build(1, n);
    }

    private List<TreeNode> build(int l, int r) {
        String key = l + "," + r;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        List<TreeNode> res = new ArrayList<>();
        if (l > r) {
            res.add(null);
            memo.put(key, res);
            return res;
        }

        for (int root = l; root <= r; root++) {
            List<TreeNode> left = build(l, root - 1);
            List<TreeNode> right = build(root + 1, r);

            for (TreeNode a : left) {
                for (TreeNode b : right) {
                    TreeNode node = new TreeNode(root);
                    node.left = a;
                    node.right = b;
                    res.add(node);
                }
            }
        }

        memo.put(key, res);
        return res;
    }
}

// build(l, r) 返回区间内所有 BST。
func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return []*TreeNode{}
    }
    memo := make(map[[2]int][]*TreeNode)
    return buildTrees(1, n, memo)
}

func buildTrees(l int, r int, memo map[[2]int][]*TreeNode) []*TreeNode {
    key := [2]int{l, r}
    if val, ok := memo[key]; ok {
        return val
    }

    res := make([]*TreeNode, 0)
    if l > r {
        res = append(res, nil)
        memo[key] = res
        return res
    }

    for root := l; root <= r; root++ {
        left := buildTrees(l, root-1, memo)
        right := buildTrees(root+1, r, memo)
        for _, a := range left {
            for _, b := range right {
                node := &TreeNode{Val: root, Left: a, Right: b}
                res = append(res, node)
            }
        }
    }

    memo[key] = res
    return res
}

复杂度分析

时间复杂度：$O(n \cdot C_n)$，其中 $C_n$ 是第 n 个卡特兰数，量级约为 $4^n / n^{1.5}$。凭什么？答案本身就有 $C_n$ 棵树，光是把它们的根节点列出来就跑不掉这个量级；记忆化保证每个区间的子树集合只构造一次，主要开销落在最外层区间的笛卡尔积上，每生成一棵树需要 $O(1)$ 次新建根节点、而一棵树的规模是 $O(n)$，因此总量与 $n \cdot C_n$ 同阶。n 上限只有 8，实际是 1430 棵树的规模。

空间复杂度：$O(n \cdot C_n)$。凭什么？返回结构里所有区间的方案列表都被记忆表长期持有，最大的一层就有 $C_n$ 个根节点，加上各层缓存的子树，总节点数与树的总规模同阶；递归深度只有 $O(n)$，相比之下可以忽略。如果去掉记忆化，节点会被重复构造，空间反而更大。

关键点总结

二叉搜索树的子树取值范围一定是连续区间：这是把「集合划分」降级成「区间划分」的根本原因，也是状态可以只用 (l, r) 两个整数刻画的原因。遇到与 BST 结构有关的题，先把这条性质写在纸上。

要「所有方案」时，递归函数的返回值就该是列表：返回单个最优解和返回全部解，写法差别很大——前者用 min/max 合并，后者用笛卡尔积合并。想清楚要什么再定函数签名，能避免中途重写。

空区间必须返回含 null 的列表：这是本题最核心的边界设计。它把「空树」当成一种合法方案参与组合，使得叶子节点的构造无需任何特判，笛卡尔积的循环自然执行一次。返回空列表会让整条分支消失。

组合时每一对都要新建根节点：把 new TreeNode(root) 提到双重循环外面是致命错误，所有组合会共享同一个对象、互相覆盖左右指针。凡是「在循环里拼装结构」的题，都要问一句「这个对象是不是被多个结果共享了」。

子树共享是允许的，根节点复用不是：判题只比对结构，多棵树指向同一棵子树实例完全没问题，这正是记忆化能生效的前提；但根节点的左右指针会在组装时被写入，所以必须每次新建。

面试视角：先说 BST 的区间性质，再定义 build(l, r) 的语义，再讲基例返回 [null] 的理由，最后补记忆化，是一个非常完整的表达链条。面试官常见的追问是「和 96 题有什么关系」——答案是 96 只需要方案数，递推式 $C_n = \sum C_i C_{n-1-i}$ 正是本题笛卡尔积的计数版本，把「构造」换成「相乘」即可，复杂度从指数降到 $O(n^2)$。

易错点总结

错误写法：l > r 时返回空列表而不是 [null]。用例 n = 1 → build(1,1) 中 root = 1 的左右子树列表都是空的，双重循环一次都不执行，res 为空，函数返回空列表而不是那棵单节点树；正确答案有 1 棵树。

错误写法：把 new TreeNode(root) 提到双重循环外面复用。用例 n = 3 → root = 1 时左子树只有 null、右子树有两棵，两次组合写的是同一个节点对象，第二次赋值把右指针从「2→右3」覆盖成「3→左2」，结果列表里两个元素指向同一棵树，答案少一棵且内容重复。

错误写法：把左右子树的角色写反，build(root+1, r) 挂到 left 上。用例 n = 2 → 得到根 1 左挂 2、根 2 左挂 1 这类结构，其中「1 的左子是 2」违反了 BST 性质（左子必须更小），判题直接判错，而不是「顺序不同但等价」。

错误写法：root 的枚举范围写成 l 到 r-1 或 l+1 到 r。用例 n = 3 → 少枚举一个根，只能得到 3 棵或 4 棵树，正确答案是 5 棵；区间里每个值都必须有当根的机会。

错误写法：记忆化的键只用左端点 l。用例 n = 3 → build(1, 1) 与 build(1, 2) 键冲突，后者会直接拿到前者缓存的单节点树，最终只返回 3 棵树；区间需要两个端点才能唯一确定。

错误写法：Java 里 memo 声明为静态字段。用例连续判两组数据 n = 3 再 n = 2 → 第二次调用会命中第一次残留的 build(1, 2) 等缓存，虽然结构恰好仍正确，但多组用例间共享可变状态在带随机顺序的评测里极易出问题，同时节点对象跨用例共享会让内存无法回收。记忆表应是实例字段或作为参数传递。

错误写法：为「去重」额外做一次树的同构比较。用例 n = 8 → 1430 棵树两两比较约一百万次、每次还要遍历整棵树，白白多出一个数量级；按根枚举天然不重复（根值不同或子树形状不同），根本不需要判重。

错误写法：先生成全排列再逐个插入建树。用例 n = 8 → $8! = 40320$ 个排列，其中大量排列生成同一棵树，不仅要额外去重，而且插入建树的顺序逻辑本身也容易写错；从根枚举出发是唯一干净的路径。

错误写法：Go 里把 memo 声明成包级变量。用例多组测试 → 与 Java 静态字段同样的问题，且并发评测时会出现 map 的并发读写 panic；把 memo 作为参数在递归间传递是最稳的做法。

错误写法：递归返回后修改缓存里的列表。用例 n = 3 → 若上层拿到 build(1, 1) 的结果后直接 append 或改动其中元素，缓存被污染，下一次命中同一区间时拿到的是被改过的列表，会凭空多出或丢失方案。缓存返回的列表只能读不能写。

相似题目

题目	难度	考察点
96. 不同的二叉搜索树	中等	同样按根切分区间，但只统计数量，笛卡尔积退化成乘法，可压成 $O(n^2)$ 递推
241. 为运算表达式设计优先级	中等	同为「枚举分割点后左右做笛卡尔积」，但分割依据是运算符位置且要合并成数值
22. 括号生成	中等	同样穷举所有合法结构，但用左右括号计数剪枝，靠回溯而非区间分治
46. 全排列	中等	穷举时需要显式撤销选择，路径是一条而非一棵树，没有子问题可复用
131. 分割回文串	中等	枚举的是切分位置且需要回文校验，方案是线性划分而不是二叉结构
93. 复原 IP 地址	中等	同样穷举全部合法方案，但段数固定为四且每段有取值范围校验，靠剪枝控制规模