记忆化递归求解不同二叉搜索树数量的时间与空间复杂度是多少？

你对空间复杂度的分析是正确的，但时间复杂度的判断不准确，实际时间复杂度为O(n³)。

空间复杂度验证 #

你提到的「总共有n²种不同的节点值区间组合」是对的，所有满足1<=low<=high<=n的区间总数为n(n+1)/2，属于O(n²)量级。记忆化缓存会存储每个区间的计算结果，递归栈的最大深度为n（远小于n²），因此整体空间复杂度确实是O(n²)。

时间复杂度修正 #

你漏算了每个区间内部选择根节点的循环开销：

• 长度为k的区间（即区间内有k个节点）共有n - k + 1个
• 每个长度为k的区间，需要遍历k次选择根节点，每次遍历调用左右子区间的已缓存结果（O(1)读取）
• 总运算量为求和式：sum(k=1到n) k*(n-k+1) = n(n+1)(n+2)/6，属于O(n³)量级，因此时间复杂度是O(n³)而非O(n²)。

代码小优化建议 #

你当前用low * 100 + high作为缓存键的方式，在n大于99时会出现键冲突（比如low=1,high=101和low=2,high=1的计算结果都是201），如果需要适配更大的n，可以改用字符串拼接low + "," + high或者Pair类型作为缓存键。

补充：该问题的本质 #

这个问题的计算结果就是第n个卡特兰数，你可以用一维动态规划的方式将时间复杂度优化到O(n²)：定义dp[i]为i个节点能构成的不同BST数量，递推式为dp[i] = sum(j=0到i-1) dp[j] * dp[i-1-j]，相比记忆化DFS减少了区间枚举的冗余，实现更简洁效率也更高。

原实现代码 #

class Solution {
    public int numTrees(int n) {
        
        // structrually unique BST with value from 1 to n
        // same structure but different number? no, one way to arrange node
        // from 1 to n start
        // left has num candid - 1 to 1
        // right has num candid + 1 to n
        
        Map<Integer, Integer> memo = new HashMap<>();
        
        return numWays(1, n, memo);
    }
    
    
    private int numWays(int low, int high, Map<Integer, Integer> memo) {
        
        if(memo.containsKey(low * 100 + high)) {
            return memo.get(low * 100 + high);
        }
        
        if(low >= high) return 1;
        int ans = 0;
        for(int i = low; i <= high; i++) {
            ans = ans + numWays(low, i - 1, memo) * numWays(i + 1, high, memo);
        }
        memo.put(low * 100 + high, ans);
        return ans;
    }
}

内容的提问来源于stack exchange，提问作者Jialin Zhen