LeetCode 96. 不同的二叉搜索树问题给定整数n求由1...n为节点组成的互不相同的二叉搜索树有多少棵。思路DP设dp[i]表示i个节点能组成的 BST 数量。以j1 ≤ j ≤ i为根左子树有j-1个节点右子树有i-j个节点。状态转移dp[i] Σ dp[j-1] * dp[i-j]初始化dp[0] 1空树只有 1 种classSolution{publicintnumTrees(intn){int[]dpnewint[n1];dp[0]1;for(inti1;in;i){for(intj1;ji;j){dp[i]dp[j-1]*dp[i-j];}}returndp[n];}}复杂度时间O(n²)空间O(n)。验证几个值n 1→ 1n 2→ 2n 3→ 5n 4→ 14这实际上算的是卡特兰数有兴趣也可以直接用公式C(n) C(2n, n) / (n 1)计算。进阶如果需要返回具体的树结构列表不只是数量可以看一下 LeetCode 95. 不同的二叉搜索树 II用回溯即可解决。 kimi LeetCode 96. 不同的二叉搜索树 Java实现
LeetCode 96. 不同的二叉搜索树问题给定整数n求由1...n为节点组成的互不相同的二叉搜索树有多少棵。思路DP设dp[i]表示i个节点能组成的 BST 数量。以j1 ≤ j ≤ i为根左子树有j-1个节点右子树有i-j个节点。状态转移dp[i] Σ dp[j-1] * dp[i-j]初始化dp[0] 1空树只有 1 种classSolution{publicintnumTrees(intn){int[]dpnewint[n1];dp[0]1;for(inti1;in;i){for(intj1;ji;j){dp[i]dp[j-1]*dp[i-j];}}returndp[n];}}复杂度时间O(n²)空间O(n)。验证几个值n 1→ 1n 2→ 2n 3→ 5n 4→ 14这实际上算的是卡特兰数有兴趣也可以直接用公式C(n) C(2n, n) / (n 1)计算。进阶如果需要返回具体的树结构列表不只是数量可以看一下 LeetCode 95. 不同的二叉搜索树 II用回溯即可解决。 RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
