#

Info

数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
95. Unique Binary Search Trees II	95. 不同的二叉搜索树 II	🟠
96. Unique Binary Search Trees	96. 不同的二叉搜索树	🟠

Info

在开头先打个广告，我的 手把手刷二叉树课程 按照公式和套路讲解了 150 道二叉树题目，只需一顿饭钱，就能手把手带你刷完二叉树分类的题目，迅速掌握递归思维，让你豁然开朗。我绝对有这个信心，信不信，可以等你看完我的二叉树算法系列文章再做评判。

之前写了两篇手把手刷 BST 算法题的文章，第一篇 讲了中序遍历对 BST 的重要意义，第二篇 写了 BST 的基本操作。

本文就来写手把手刷 BST 系列的第三篇，循序渐进地讲两道题，如何计算所有有效 BST。

第一道题是力扣第 96 题「不同的二叉搜索树」，给你输入一个正整数 n，请你计算，存储 {1,2,3...,n} 这些值共有多少种不同的 BST 结构。

函数签名如下：

int numTrees(int n);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int numTrees(int n);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def numTrees(n: int) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func numTrees(n int) int {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var numTrees = function(n) {

};

比如说输入 n = 3，算法返回 5，因为共有如下 5 种不同的 BST 结构存储 {1,2,3}：

这就是一个正宗的穷举问题，那么什么方式能够正确地穷举有效 BST 的数量呢？

我们前文说过，不要小看「穷举」，这是一件看起来简单但是比较有技术含量的事情，问题的关键就是不能数漏，也不能数多，你咋整？

之前 手把手刷二叉树第一期 说过，二叉树算法的关键就在于明确根节点需要做什么，其实 BST 作为一种特殊的二叉树，核心思路也是一样的。

本文剩余内容为会员内容，请先购买 网站会员 ，然后 借助 Chrome 插件解锁网页 或者 点这里 跳转小鹅通查看。