小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

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

2019年11月25日 849点热度 0人点赞 0条评论

Leetcode 96:不同的二叉搜索树

题目描述

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

示例

示例

解题思路

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

示例

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

代码实现


int numTrees(int n) {     long long C = 1;     for (int i = 0; i < n; ++i)     {         C = C * 2 * (2 * i + 1) / (i + 2);     }     return (int)C; }

复杂度分析

复杂度分析

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

Leetcode 98:验证二叉搜索树

题目描述

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

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

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

题目解析

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

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

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

代码实现

bool vBST(TreeNode* root, long long lower, long long upper)
{
    if (root == nullptr)
        return true;
    int value = root->val;
    if (lower != LLONG_MIN && value <= lower)
        return false;
    if (upper !=LLONG_MAX && value >= upper)
        return false;
    return (vBST(root->left, lower, value) && vBST(root->right, value, upper));
}
bool isValidBST(TreeNode* root) {
    if (root == nullptr)
        return true;
    return vBST(root, LLONG_MIN, LLONG_MAX);
}

执行用时&内存消耗

复杂度分析

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年11月25日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
2010年8月3日-4日凌晨博客更新内容 python处理csv文件,以锡特卡气温为例 2015年全年总结 《新青年报》第一期发布 《剑指Offer》题目解析(4) 2017考研总体安排(2016.1~2016.12)
标签聚合
学习 python学习 鸟哥的linux私房菜 算法 leetcode 生活 Java linux Python 高中
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 8 个月前(10月20日) :wink:
niming 发布于 9 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号