力扣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的三种方式

相关内容

热门资讯

捷豹安卓系统车载,捷豹安卓系统... 哇，你有没有想过，当你的手机和汽车融为一体，会是怎样的体验呢？想象你正驾驶着你的捷豹，车窗外的风景如...
安卓1到10系统,安卓1.0至... 你有没有想过，手机里的安卓系统就像是我们生活中的好朋友，从青涩的少年成长为稳重的青年呢？从安卓1.0...
安卓8.0停用系统应用,提升使... 你知道吗？最近安卓系统又来了一次大动作，那就是安卓8.0系统开始停用一些系统应用了。这可真是让人有点...
安卓系统修改mtu值,轻松提升... 你有没有想过，你的安卓手机其实是个小小的电脑呢？它里面藏着许多可以自定义的秘密功能，就像修改MTU值...
安卓平板改window系统,探... 你有没有想过，你的安卓平板其实可以摇身一变，变成一个Windows系统的电脑呢？没错，就是那种可以运...
时空猎人安卓苹果系统,探索无尽... 你知道吗？最近在手机游戏圈里，有一款叫做《时空猎人》的游戏可是火得一塌糊涂呢！不管是安卓用户还是苹果...
安卓9.0系统的电视,新一代电... 亲爱的读者们，你是否也像我一样，对科技新玩意儿充满好奇？今天，我要和你聊聊一个让人眼前一亮的话题——...
小pc安装安卓系统,轻松安装安... 你有没有想过，你的小PC也能变身成为安卓系统的超级玩家呢？没错，就是那个平时默默无闻的小家伙，现在也...
高通备份安卓系统,全方位数据安... 你知道吗？在这个科技飞速发展的时代，手机备份可是个不得不提的话题。尤其是对于安卓用户来说，选择一个靠...
谷歌安卓系统有多少,从诞生到全... 你有没有想过，那个无处不在的谷歌安卓系统，究竟在全球有多少用户呢？它就像一个神秘的数字，每天都在悄悄...
fc黄金传说安卓系统,畅享复古... 你有没有听说最近安卓系统上的一款超酷的游戏——《FC黄金传说》？这款游戏可是让不少玩家都沉迷其中，今...
变小的我安卓系统,安卓系统演变... 你有没有发现，最近你的手机好像变轻了？没错，说的就是你，那个陪伴你多年的安卓系统。它悄无声息地进行了...
vivo安卓系统小彩蛋,体验科... 你知道吗？在vivo的安卓系统中，竟然隐藏着一些超有趣的小彩蛋！这些小彩蛋就像是在手机里埋下的宝藏，...
安卓系统如何强制重启,安卓系统... 手机突然卡壳了，是不是又该给它来个“大保健”了？没错，今天就来聊聊安卓系统如何强制重启。别小看这个看...
全民飞行团安卓系统,体验指尖上... 你知道吗？最近在手机游戏圈里，有个叫做“全民飞行团”的新星正在闪耀！这款游戏不仅吸引了无数玩家的目光...
安卓鸿蒙系统壁纸软件,壁纸软件... 亲爱的手机控们，你是否厌倦了单调的壁纸？想要给你的安卓手机换上充满科技感的鸿蒙系统风格壁纸？那就跟我...
安卓系统ram重新分区,提升系... 你有没有发现，你的安卓手机最近有点儿卡呢？别急，别急，今天就来给你揭秘如何给安卓系统的RAM来个重新...
迷你退出安卓系统了吗,转型新篇... 最近有没有发现你的手机上那个可爱的迷你退出图标突然不见了？别急，让我来给你揭秘迷你退出安卓系统了吗的...
华为优先使用安卓系统,打造自主... 你知道吗？最近科技圈里有个大动作，那就是华为宣布优先使用安卓系统。这可不是一个简单的决定，它背后可是...
安卓系统隐藏了设置,隐藏设置功... 你知道吗？安卓系统这个大宝藏里，竟然隐藏着一些不为人知的设置！是不是听起来就有点小激动呢？别急，今天...