跳至主要內容

 

labuladong原创数据结构二叉搜索树二叉树分解问题的思路约 1782 字大约 6 分钟

Info

新版网站会员open in new window 限时优惠;算法可视化编辑器上线,点击体验open in new window

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

LeetCode力扣难度
95. Unique Binary Search Trees IIopen in new window95. 不同的二叉搜索树 IIopen in new window🟠
96. Unique Binary Search Treesopen in new window96. 不同的二叉搜索树open in new window🟠

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

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

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

函数签名如下:

java 🟢
int numTrees(int n);

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

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

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

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

加载中...

上次编辑于: