力扣98.验证二叉搜索树
创始人
2024-05-15 04:23:57
0次

文章目录

  • 力扣98.验证二叉搜索树
    • 题目描述
    • 算法思路
    • 代码实现

力扣98.验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true
示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

算法思路

  • 基于二叉搜索树的性质：中序遍历一棵二叉搜索树将获得一个递增序列
  • 采用中序遍历的思路，对该二叉树进行中序遍历，每次遍历到的值与前一次遍历到的值比较，如果不是递增的，就返回false表示这不是一棵二叉搜索树
  • 时间复杂度O(n)

代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int pre;//前一次遍历到的值bool first;//是否是第一次遍历的标志
bool InOrder(struct TreeNode * root)
{if(root==NULL) return true; if(!InOrder(root->left)) return false;//若左子树不是二叉搜索树，返回false；if(root->val<=pre&&!first) return false;//若当前遍历的值没有比前一个大，返回falseelse { pre=root->val;  first=false; }//更新preif(!InOrder(root->right)) return false;//若右子树不是二叉搜索树，返回false；return true;
}
bool isValidBST(struct TreeNode* root){first=true;return InOrder(root);
}

在这里插入图片描述

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：NodeJS 之 fs 模块（路径动态拼接问题）

下一篇：Arduino环境下对NodeMCU ESP8266将文件直接传入flash的三种方式

相关内容

热门资讯

安卓系统文件解压缩,轻松掌握文... 你有没有遇到过这种情况：手机里下载了一大堆安卓系统文件，但是不知道怎么解压缩呢？别急，今天就来给你详...
安卓系统有深夜模式吗,揭秘深夜... 安卓系统有深夜模式吗？夜幕降临，手机屏幕的亮光在黑暗中显得格外刺眼。你是否有过这样的困扰：深夜时分，...
安卓系统a收音机,尽享无线音域 你有没有想过，在安卓手机上，除了刷剧、聊天、玩游戏，还能干点啥？今天，就让我带你一探究竟，看看安卓系...
安卓怎么退回老系统,安卓系统升... 手机用久了，是不是觉得新系统越来越卡，老系统那个熟悉的感觉又回来了？别急，今天就来教你怎么把安卓手机...
安卓系统44限制吗 最近你的安卓手机是不是突然感觉有点儿“力不从心”了呢？别急，让我来给你揭秘一下安卓系统44的限制之谜...
闪回门店系统安卓版,焕新零售体... 你有没有想过，那些曾经陪伴我们度过无数美好时光的门店，现在是不是还留在你的记忆里呢？今天，就让我带你...
安卓系统和windows同步,... 你有没有发现，手机里的照片、文档、音乐，还有那些重要的联系人信息，有时候真是让人头疼，因为它们都分散...
安卓系统在哪儿开源,从诞生到全... 你有没有想过，安卓系统这个我们每天不离手的家伙，它到底是从哪儿来的呢？没错，就是开源！今天，就让我带...
三星安卓系统711,探索创新与... 你有没有发现，最近手机圈里又掀起了一股热潮？没错，就是三星的新款手机，搭载的安卓系统7.1.1。这可...
安卓系统应用无法启动,探究无法... 手机里的安卓系统应用突然打不开，是不是让你心头一紧？别急，今天就来给你详细解析一下这个问题，让你轻松...
安卓主题仿苹果系统吗,探索苹果... 你有没有发现，最近手机界又掀起了一股风潮？那就是安卓手机上的主题设计，竟然开始模仿苹果系统的风格了！...
安卓系统盒马餐饮熟食,安卓系统... 你有没有发现，现在的生活越来越离不开手机了？尤其是安卓系统，几乎成了我们生活中不可或缺的一部分。这不...
thinkpad8安卓双系统,... 你有没有想过，一台笔记本电脑既能满足你工作时的严谨需求，又能让你在闲暇时刻畅游安卓世界？今天，就让我...
想看安卓系统u青年影院,U青年... 亲爱的读者们，你是否也和我一样，对安卓系统的电影应用充满了好奇？今天，就让我带你一起探索一个特别的地...
安卓系统王者荣耀更新慢,探究原... 最近你是不是也遇到了这个问题？每次打开王者荣耀，总是慢吞吞的，让人等得心痒痒。安卓系统的王者荣耀更新...
安卓系统怎么装ios系统软件,... 你是不是也和我一样，对安卓系统上的iOS软件垂涎欲滴呢？想象在安卓手机上流畅运行《王者荣耀》或者《原...
蓝牙系统和安卓哪个好使,谁更胜... 蓝牙系统和安卓哪个好使？这个问题，相信不少手机用户都曾纠结过。蓝牙系统，作为无线通信技术的一种，让我...
安卓系统停用怎么回事 最近你的安卓手机是不是突然有点儿“闹脾气”了？屏幕上突然弹出一个通知，告诉你安卓系统要停用了？别急，...
安卓系统照片怎么发视频 你是不是也和我一样，手机里存了好多珍贵的照片，突然想和朋友们分享一段美好的回忆呢？别急，今天就来教你...
永远会用安卓系统的手机 亲爱的手机控们，你是否也有那么一款手机，它陪伴你度过了无数个日夜，成为了你生活中不可或缺的一部分？没...