原创数据结构二叉搜索树二叉树分解问题的思路约 1770 字大约 6 分钟
Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
95. Unique Binary Search Trees II | 95. 不同的二叉搜索树 II | 🟠 |
96. Unique Binary Search Trees | 96. 不同的二叉搜索树 | 🟠 |
之前写了两篇手把手刷 BST 算法题的文章,第一篇 讲了中序遍历对 BST 的重要意义,第二篇 写了 BST 的基本操作。
本文就来写手把手刷 BST 系列的第三篇,循序渐进地讲两道题,如何计算所有有效 BST。
第一道题是力扣第 96 题「不同的二叉搜索树」,给你输入一个正整数 n
,请你计算,存储 {1,2,3...,n}
这些值共有多少种不同的 BST 结构。
函数签名如下:
java 🟢
int numTrees(int n);
cpp 🤖
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
int numTrees(int n);
python 🤖
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def numTrees(n: int) -> int:
go 🤖
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func numTrees(n int) int {}
javascript 🤖
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var numTrees = function(n) {
};
比如说输入 n = 3
,算法返回 5,因为共有如下 5 种不同的 BST 结构存储 {1,2,3}
:
![](/algo/images/BST3/2.jpg)
这就是一个正宗的穷举问题,那么什么方式能够正确地穷举有效 BST 的数量呢?
我们前文说过,不要小看「穷举」,这是一件看起来简单但是比较有技术含量的事情,问题的关键就是不能数漏,也不能数多,你咋整?
之前 手把手刷二叉树第一期 说过,二叉树算法的关键就在于明确根节点需要做什么,其实 BST 作为一种特殊的二叉树,核心思路也是一样的。