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

Categories:

题目描述
思路分析
1. 解法一：递归枚举 + 记忆化（推荐）
相似题目

题目描述

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

思路分析

解法一：递归枚举 + 记忆化（推荐）

核心思路：

以每个值作为根，递归生成左子树与右子树的所有组合。

build(l, r) 返回区间内所有 BST。

用记忆化避免重复构造区间。

复杂度分析：

时间复杂度：O(Cn)，其中 Cn 为第 n 个卡特兰数。

空间复杂度：O(Cn)。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

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
}

相似题目

题目	难度	考察点
96. 不同的二叉搜索树	中等	卡特兰数
109. 有序链表转换二叉搜索树	中等	BST 构造
94. 二叉树的中序遍历	简单	递归
98. 验证二叉搜索树	中等	BST
230. 二叉搜索树中第K小的元素	中等	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/70602100