【leetcode】96. 不同的二叉搜索树
leetcode 刷题笔记,96. 不同的二叉搜索树。
96. 不同的二叉搜索树
题目
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
思路
这道题是道动态规划的题目,动态规划的最重要的就是找到迭代的方程。
可以先举例几个不同的二叉搜索树情况,再找找有没有啥规律可循。首先是最简单的单个节点和两个节点的树,单个节点的二叉树只有 1 种情况,两个节点的二叉树有 2 种情况。
如果是三个节点的二叉搜索树呢?以 leetcode 给出的示例图
从图中可以总结出三种不同的情况,假设 f(x)
为有 x 元素的二叉搜索树的种类个数。
- 当 1 为根节点的时候,左子树为空,右子树 2 个元素,那么当前树的形态数量就是
f(0) * f(2)
,即只由右边的两个元素的树的形态数量决定; - 当 2 为根节点的时候,左右子树都有 1 个元素,此时树的形态数量是
f(1) * f(1)
,即由两个元素只有 1 的树的形态数量组合决定; - 当 3 为根节点的时候,右子树为空,左子树 2 个元素,这和 1 为根节点的情况类似,即当前树只由左边两个元素的树的形态数量决定,
f(2) * f(0)
;
由此可得 x 为 3 的时候二叉搜索树的种类的计算公式
这里就还需要确定一下 f(0)
应该是什么值了,因为空树也可以视作树的一种情况,再加上在当前的递推公式种涉及到了对 f(0)
的计算,所以应该将其初始化为 1。否则计算的时候相关的值都为 0 了。
上面的这个公式结论,还可以推广到 i 个节点的树的情况:
我们需要计算有 n 个节点的二叉搜索树种类,可以用这个递推公式一直从 1 计算到 n,即可得到最终的结果。其本质就是将一个大的二叉搜索树不断拆分成小的树。
关于拆分这一点,可以参考一篇写的还不错的题解,详细介绍了整个拆分的思路。
我们可以认为我们需要遍历的是一个 1 到 n 的数组,那么从这个数组中,不管从哪一个位置 “提起” 这棵树,最终得到的都是一个符合二叉搜索树规定的树(可以参考从有序数组构造二叉搜索树的 OJ 题)。这样我们就可以使用二分的思想不断将树拆分,直到拆分成只有 1 个元素的树的情况。
那么代码中应该怎么处理呢?这里需要多层循环,我们需要将计算公式改成循环的累加(总不可能一直写个很长的公式吧)
首先外层循环是从 1 递推到 n,内层循环是进行每一次有 i 个元素的二叉搜索树的节点数量计算。这样就实现了递推的计算。
1 | // i代表当前树中有几个节点 |
代码
完整代码如下,注意 vector 中的所有元素需要初始化为 0,否则无法正常进行累加。根据上述思路将 v[0]=1
初始化,然后用循环一直计算到 n,最后 v[n]
就是我们需要的结果。
1 | class Solution { |
- 最新
- 最热
- 最早
- 作者
点击重新获取 | 打开控制台