LeetCode 95. 不同的二叉搜索树 II Java实现题意给整数 n 生成由 1 ~ n 节点构成的所有不同二叉搜索树。二叉搜索树左子树全部 根右子树全部 根。思路递归枚举根节点 i [1,i‑1] 构造左子树集合 [i1,n] 构造右子树集合左右两两组合生成所有树。TreeNode定义javaclass 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;}}完整代码javaimport 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 ListTreeNode build(int l, int r) { ListTreeNode res new ArrayList(); // 空区间返回null节点用于组合 if(l r) { res.add(null); return res; } // 枚举每一个i作为根 for(int i l; i r; i) { ListTreeNode leftTrees build(l, i - 1); ListTreeNode 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; }}核心要点递归区间 [l,r] 当 lr 必须返回包含 null 的list否则无法拼接左右子树根为 i 左子树来自 [l,i‑1] 全部BST右子树来自 [i1,r] 全部BST双重循环做笛卡尔积每一组左、右子树新建根节点组装n0返回空集合。复杂度时间O(G_n)G_n是第n个卡特兰数卡特兰数量级O(\frac{4^n}{n\sqrt{n}})空间O(G_n)存储全部树进阶记忆化DP优化重复区间缓存javaimport java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;class Solution {private MapString,List memo;public ListTreeNode generateTrees(int n) { if(n 0) return new ArrayList(); memo new HashMap(); return build(1,n); } private ListTreeNode build(int l, int r) { String key l , r; if(memo.containsKey(key)) return memo.get(key); ListTreeNode res new ArrayList(); if(l r) { res.add(null); memo.put(key,res); return res; } for(int il;ir;i){ ListTreeNode left build(l,i-1); ListTreeNode right build(i1,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版本吗