当前位置: 首页 > news >正文

181.二叉树:验证二叉树(力扣)

代码解决

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 用于记录中序遍历过程中的前一个节点TreeNode* pre = nullptr;bool isValidBST(TreeNode* root) {// 如果根节点为空,说明是一棵空树,返回trueif(root == nullptr) return true;// 遍历左子树bool left = isValidBST(root->left);// 如果当前节点的值小于等于中序遍历的前一个节点值(pre)if(pre != nullptr && pre->val >= root->val)return false; // 不满足BST定义,返回false// 更新前一个节点为当前节点pre = root;// 继续遍历右子树bool right = isValidBST(root->right);// 返回左右子树是否都满足BST的结果return left && right;}
};

代码使用了递归的方法。主要思路是从根节点开始,递归地检查左右子树。在递归过程中,使用一个全局变量 pre 来记录中序遍历过程中的前一个节点,以确保每个节点的值都大于前一个节点的值。

这里简要解释一下代码的工作流程:

  1. 定义一个全局变量 pre 用于记录中序遍历过程中的前一个节点。
  2. 定义一个辅助函数 isValidBST,它接受当前节点作为参数。
  3. 首先检查当前节点是否为空,如果是,返回 true
  4. 递归地检查左子树,并返回其结果。
  5. 如果当前节点的值小于等于中序遍历的前一个节点值 pre,返回 false
  6. 更新 pre 为当前节点。
  7. 递归地检查右子树,并返回其结果。
  8. 返回左右子树都满足条件的布尔值。

这个算法的时间复杂度是 O(n),因为每个节点都会被访问一次,其中 n 是树中节点的数量。空间复杂度也是 O(n),因为需要存储递归调用的栈。

相关文章:

  • STM32CUBEIDE使用技巧
  • docker——基础知识
  • 08_第八章 微头条项目开发
  • Spring系统学习 - Bean的作用域
  • 震坤行坤合供应链荣获“2024 LOG低碳供应链物流-最具影响力品牌商”
  • 快捷键专栏 IDEA、Navicat、电脑、Excle、Word等
  • SpringCash
  • Java--数组小结
  • 【Spine学习06】之IK约束绑定,制作人物待机动画,图表塞贝尔曲线优化动作
  • Java之等待唤醒方法
  • 如何成为一名黑客?小白必学的12个基本步骤
  • 【设计模式之组合模式 -- C++】
  • 在项目中使用Volta控制node版本
  • 【css】html 标初始化CSS样式(初学者必看)
  • VUE之重定向redirect
  • [数据结构]链表的实现在PHP中
  • 【140天】尚学堂高淇Java300集视频精华笔记(86-87)
  • classpath对获取配置文件的影响
  • HTTP 简介
  • log4j2输出到kafka
  • Promise面试题,控制异步流程
  • Redis在Web项目中的应用与实践
  • springboot_database项目介绍
  • Vue ES6 Jade Scss Webpack Gulp
  • Webpack4 学习笔记 - 01:webpack的安装和简单配置
  • 案例分享〡三拾众筹持续交付开发流程支撑创新业务
  • 短视频宝贝=慢?阿里巴巴工程师这样秒开短视频
  • 利用DataURL技术在网页上显示图片
  • 聊聊hikari连接池的leakDetectionThreshold
  • 前端面试题总结
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • [Shell 脚本] 备份网站文件至OSS服务(纯shell脚本无sdk) ...
  • Spring第一个helloWorld
  • 容器镜像
  • #QT(QCharts绘制曲线)
  • (2)MFC+openGL单文档框架glFrame
  • (3)(3.2) MAVLink2数据包签名(安全)
  • (更新)A股上市公司华证ESG评级得分稳健性校验ESG得分年均值中位数(2009-2023年.12)
  • (六) ES6 新特性 —— 迭代器(iterator)
  • (每日持续更新)jdk api之FileFilter基础、应用、实战
  • (南京观海微电子)——COF介绍
  • (十七)devops持续集成开发——使用jenkins流水线pipeline方式发布一个微服务项目
  • (五) 一起学 Unix 环境高级编程 (APUE) 之 进程环境
  • (原)记一次CentOS7 磁盘空间大小异常的解决过程
  • (转)关于pipe()的详细解析
  • (转)原始图像数据和PDF中的图像数据
  • ****三次握手和四次挥手
  • .Net core 6.0 升8.0
  • .Net mvc总结
  • .Net 基于MiniExcel的导入功能接口示例
  • .NET4.0并行计算技术基础(1)
  • .net开发引用程序集提示没有强名称的解决办法
  • .net快速开发框架源码分享
  • .net专家(高海东的专栏)
  • @SuppressWarnings注解