×

由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁
按照操作即可解锁本站全部文章

公众号

东哥带你刷二叉搜索树(构造篇)

通知: 数据结构精品课 已更新到 V1.9,点击这里体验 刷题全家桶

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

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

———–

PS: 刷题插件 集成了手把手刷二叉树功能,按照公式和套路讲解了 150 道二叉树题目,可手把手带你刷完二叉树分类的题目,迅速掌握递归思维。

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

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

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

函数签名如下:

int numTrees(int n);

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

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

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

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

_____________

应合作方要求,本文不便在此发布,请扫码关注回复关键词「BST」或 点这里 查看:

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释