2019-11-25  76 views 评论

Leetcode题目解析(191125):96&98

 标签:

Leetcode 96:不同的二叉搜索树

题目描述

给定一个整数n,求以1...n为节点的二叉搜索树有多少种?

示例

示例

解题思路

可以使用动态规划解,但是这个题同样也是一个卡塔兰数问题。卡塔兰数的应用主要有:找零钱问题、三角网格问题、括号排列问题、球盒问题等。卡塔兰数的数学表达式为

示例

所以代码只需要实现这个式子即可,时间复杂度为O(n),空间复杂度为O(1)。

代码实现

复杂度分析

复杂度分析

时间复杂度为O(n),空间复杂度为O(1)。

Leetcode 98:验证二叉搜索树

题目描述

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

题目解析

二叉树的题一般比较容易想到的就是用递归去做,在这里我们用一个名为vBST的子函数去做,由于是二叉搜索树,它的特征就是:

  • 节点的左子树只包含小于当前节点的数;
  • 节点的右子树只包含大于当前节点的数。

所以在这个子函数里面我们要传三个参数:当前结点、如果是二叉搜索树时的最小值和最大值。那么对于这三个值,我们分别假设为value、lower和upper。这样就存在三种情况:当前结点为空,那么自然返回true;若lower值存在(若是判断根节点等情况下,lower值可能不存在,所以传递的时候要传递一个可取值的最小值,由于示例中给出了超过int类型的数值,所以这里我们使用了long long类型),那么value小于lower的话,说明当前结点小于其根结点的值,自然不是二叉搜索树,返回false;同理对upper也是如此。如果当前值符合要求,则一层一层递归下去即可。

代码实现

执行用时&内存消耗

复杂度分析

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: