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

约 6 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
动态规划 树 二叉树 回溯 二叉搜索树

题目描述

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

image-20260928225357168

题意分析

使用 1..n 中的每个值各一次，生成所有结构不同的二叉搜索树，返回它们的根节点，顺序不限。每棵树都必须包含全部值，并满足左子树值小于根、右子树值大于根。

解法：递归枚举 + 记忆化

核心思路

[!blue]

定义 build(l, r) 返回恰好使用值域 [l, r] 的全部二叉搜索树。选定根值 root 后，搜索树性质强制所有较小值放在左子树，所有较大值放在右子树，所以左右子问题分别为 [l, root - 1] 和 [root + 1, r]。

左右结构相互独立，将左侧每个候选与右侧每个候选逐对组合，每一对新建一个根节点并连接两棵子树。任意合法树都有唯一根值和唯一的左右结构，因此枚举所有根、所有左右配对既不会遗漏，也不会产生重复结构。

当 l > r 时，当前一侧没有节点，但“选择空树”仍是一种合法选择，所以必须返回含一个空节点的列表。这样另一侧的每个候选都能与空树配对；如果返回空列表，双重循环一次也不会执行，连叶节点都无法生成。

不同父问题会请求同一值域的全部结构，用 (l, r) 缓存即可避免重复生成。组合时只新建根，直接引用已生成的左右子树，之后不再修改这些子树。因此多个结果可能共享子树节点，这份实现按只读方式使用已构造结果。

解题步骤

  • 从 build(1, n) 开始；代码对 n = 0 直接返回空结果列表。
  • 用区间两个端点作为缓存键，若已有结果则直接返回。
  • 空区间构造仅含 null / nil 的候选列表并缓存。
  • 对非空区间枚举每个根，递归取得左右候选，遍历其笛卡尔积，每对候选新建根并加入结果。
  • 缓存当前区间的全部结果后返回，递归区间每次缩小，最终都到达空区间。

代码实现

// 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
}

复杂度分析

设 C_n 为第 n 个卡特兰数，也就是最终返回的树的数量。

  • 时间复杂度：可用 $O(nC_n)$ 作为保守上界。必须枚举全部结果；当前实现缓存各区间，每次左右配对只创建一个根，并未为每个结果深拷贝全部 n 个节点。
  • 空间复杂度：$O(nC_n)$ 保守上界，计入结果节点和区间缓存；递归栈深度为 $O(n)$。共享子树使实际节点分配量小于逐棵独立复制的实现。

关键点总结

[!green]

  • 根值确定左右值域，左右候选的所有配对构成当前根的全部结构。
  • 含一个空节点的列表表示一种空树选择，空列表则表示没有可组合方案。
  • 缓存按完整区间区分，组合时新建根、只读复用子树。

易错点总结

[!yellow]

  • 空区间若返回空列表，会让所有需要空孩子的树都无法参与组合。
  • 每个左右配对必须创建新根；反复修改同一个根对象会覆盖已加入结果的树。
  • 只按一个端点缓存，无法区分使用不同值域的子问题。
  • 已缓存的子树可能被多个结果引用，不能在组合后继续修改其节点或左右链接。

相似题目

题目 难度 关联与区别
96. 不同的二叉搜索树 中等 分割根节点并组合左右子树的结构相同，原题只计数，本题需要构造所有不同树。
894. 所有可能的真二叉树 中等 同样递归组合所有子树形状，原题要求每个节点要么无孩子要么有两个孩子。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/70602100
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！