千问 LeetCode 95. 不同的二叉搜索树 II Java实现

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

题意：给整数 n ，生成由 1 ~ n 节点构成的所有不同二叉搜索树。
二叉搜索树：左子树全部 < 根，右子树全部 > 根。
思路：递归枚举根节点 i ， [1,i‑1] 构造左子树集合， [i+1,n] 构造右子树集合，左右两两组合生成所有树。

TreeNode定义：

java

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

完整代码

java

import java.util.ArrayList;
import java.util.List;

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

// 生成 [l, r]区间所有BST private List<TreeNode> build(int l, int r) { List<TreeNode> res = new ArrayList<>(); // 空区间，返回null节点用于组合 if(l > r) { res.add(null); return res; } // 枚举每一个i作为根 for(int i = l; i <= r; i++) { List<TreeNode> leftTrees = build(l, i - 1); List<TreeNode> rightTrees = build(i + 1, r); // 左右子树笛卡尔积组合 for(TreeNode left : leftTrees) { for(TreeNode right : rightTrees) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; res.add(root); } } } return res; }

}

核心要点

1. 递归区间 [l,r] ，当 l>r 必须返回包含 null 的list，否则无法拼接左右子树；
2. 根为 i ，左子树来自 [l,i‑1] 全部BST，右子树来自 [i+1,r] 全部BST；
3. 双重循环做笛卡尔积，每一组左、右子树新建根节点组装；
4. n=0返回空集合。

复杂度

• 时间：O(G_n)，G_n是第n个卡特兰数，卡特兰数量级O(\frac{4^n}{n\sqrt{n}})
• 空间：O(G_n)存储全部树

进阶：记忆化DP优化（重复区间缓存）

java

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

class Solution {
private Map<String,List> memo;

public List<TreeNode> generateTrees(int n) { if(n == 0) return new ArrayList<>(); memo = new HashMap<>(); 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 i=l;i<=r;i++){ List<TreeNode> left = build(l,i-1); List<TreeNode> right = build(i+1,r); for(TreeNode ln : left){ for(TreeNode rn : right){ TreeNode root = new TreeNode(i); root.left = ln; root.right = rn; res.add(root); } } } memo.put(key,res); return res; }

}

需要 Python / Rust / C++版本吗？