C语言面试题之合法二叉搜索树

合法二叉搜索树

实例要求

  • 实现一个函数,检查一棵二叉树是否为二叉搜索树;
示例 1:
输入:2/ \1   3
输出: true
示例 2:
输入:5/ \1   4/ \3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ,但是其右子节点值为 4

实例分析

  • 1、递归地检查二叉树是否为二叉搜索树;
  • 2、在递归的过程中,传递了每个节点的值应该满足的最小值和最大值范围;
  • 3、初始调用时,根节点的值的范围为负无穷到正无穷;

示例代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool isValidBSTUtil(struct TreeNode* root, long long minVal, long long maxVal) {if (root == NULL) {return true;}if (root->val <= minVal || root->val >= maxVal) {return false;}return isValidBSTUtil(root->left, minVal, root->val) && isValidBSTUtil(root->right, root->val, maxVal);
}bool isValidBST(struct TreeNode* root) {return isValidBSTUtil(root, LLONG_MIN, LLONG_MAX);
}

代码解释

  • 1、这个实现使用了递归函数 isValidBSTUtil,该函数接受三个参数:当前节点指针 root、当前节点允许的最小值 minVal、当前节点允许的最大值 maxVal
  • 2、函数首先检查当前节点是否为空,如果是空节点则直接返回 true,因为空节点满足二叉搜索树的条件;
  • 3、接着,函数检查当前节点的值是否在允许的范围内,即是否大于 minVal 且小于 maxVal;
  • 4、如果不在范围内,则返回 false,表示当前节点不满足二叉搜索树的定义;
  • 5、最后,函数通过递归调用自身来检查当前节点的左子树和右子树,更新范围值为当前节点的值作为新的上界或下界
  • 6、如果左子树和右子树都是二叉搜索树,则返回 true,否则返回 false;

运行结果

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/304975.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VS2022使用属性表快速设置OpenCV工程属性

1.创建C控制台应用 2.配置工程 3.打开工程后,为工程添加属性表 打开属性管理器窗口,选择Debug|x64 然后右击选择添加新的项目属性表 并命名为opencv490_debug_x64 点击添加 Debug版本属性表添加成功 使用相同方法添加Release版本属性表 双击debug版本属性表并添加包含目录 添…

90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装)

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…

Github第一Star数的国产免费开源防火墙--雷池社区版初步体验

前言 近期准备搭建一个博客网站&#xff0c;用来存储工作室同学们的学习笔记。服务器准备直接放在公网上&#xff0c;方便大家随时随地的上传和浏览&#xff0c;为了防止网站被人日穿成为肉鸡&#xff0c;一些防御措施还是要部署的。 首先明确自己的需求&#xff1a; 零成本…

【Python】控制台进度条

在Python开发中&#xff0c;有时需要向用户展示一个任务的进度&#xff0c;以提供更好的交互体验。下面我将展示如何使用Python来创建一个简单的控制台进度条。 效果&#xff1a; 代码&#xff1a; import time import sys def print_progress_bar(completed, total, length…

Windows搭建Jellyfin影音服务结合内网穿透实现公网访问本地视频文件

文章目录 1. 前言2. Jellyfin服务网站搭建2.1. Jellyfin下载和安装2.2. Jellyfin网页测试 3.本地网页发布3.1 cpolar的安装和注册3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5. 结语 1. 前言 随着移动智能设备的普及&#xff0c;各种各样的使用需求也被开发出来&…

【Web】NSSRound#1-20 Basic 刷题记录(全)

目录 [NSSRound#1 Basic]basic_check [NSSRound#1 Basic]sql_by_sql [NSSCTF 2nd]php签到 [NSSCTF 2nd]MyBox [NSSCTF 2nd]MyBox(revenge) [NSSCTF 2nd]MyHurricane [NSSCTF 2nd]MyJs [NSSRound#3 Team]This1sMysql [NSSRound#3 Team]path_by_path [NSSRound#…

二叉树应用——最优二叉树(Huffman树)、贪心算法—— Huffman编码

1、外部带权外部路径长度、Huffman树 从图中可以看出&#xff0c;深度越浅的叶子结点权重越大&#xff0c;深度越深的叶子结点权重越小的话&#xff0c;得出的带权外部路径长度越小。 Huffman树就是使得外部带权路径最小的二叉树 2、如何构造Huffman树 &#xff08;1&#xf…

【Python-MP4文体提取】

Python-MP4文体提取 ■ pip 和 setuptools工具■ OpenCV和Tesseract■ Tesseract OCR V5.0安装教程&#xff08;Windows&#xff09;■ 1. 运行程序出现如下问题&#xff1a;我们需要安装Tesseract OCR■ 2. 下载Tesseract-OCR■ 3. 安装Tesseract-OCR■ 4. 添加到环境变量的系…

Golang中的上下文-context包的简介及使用

文章目录 简介context.Background()上下文取消函数上下文值传递建议Reference 简介 Go语言中的context包定义了一个名为Context的类型&#xff0c;它定义并传递截止日期、取消信号和其他请求范围的值&#xff0c;形成一个链式模型。如果我们查看官方文档&#xff0c;它是这样说…

Ollama利用嵌入模型实现RAG应用

Ollama支持embedding models嵌入模型&#xff0c;从而支持RAG&#xff08;retrieval augmented generation&#xff09;应用&#xff0c;结合文本提示词&#xff0c;检索到文档或相关数据。嵌入模型是通过训练生成向量嵌入&#xff0c;这是一长串数字数组&#xff0c;代表文本序…

练习 21 Web [GXYCTF2019]BabySQli

SQL联合查询&#xff0c;注意有源码看源码&#xff0c;Base64以及32的区别&#xff0c;MD5碰撞 打开后有登录框&#xff0c;先随意登录尝试 只有输入admin才是返回wrong pass&#xff01; 其他返回wrong user 所以用户名字段一定要输入admin 养成好习惯&#xff0c;先查看源码…

kali上python3切换python2环境

一、然后打开终端输入 python --version 二、 打开终端分别输入下面两条命令&#xff1a; update-alternatives --install /usr/bin/python python /usr/bin/python2 100 update-alternatives --install /usr/bin/python python /usr/bin/python3 150 三、 如果需要切换python版…

Windows系统C盘空间优化进阶:磁盘清理与Docker日志管理

Windows系统C盘空间优化进阶&#xff1a;磁盘清理与Docker日志管理 文章目录 Windows系统C盘空间优化进阶&#xff1a;磁盘清理与Docker日志管理磁盘清理工具 使用“运行”命令访问磁盘清理利用存储感知自动管理空间清理WinSxS文件夹结合手动清理策略 小结删除临时文件总结&…

流式密集视频字幕

流式密集视频字幕 摘要1 IntroductionRelated Work3 Streaming Dense Video Captioning Streaming Dense Video Captioning 摘要 对于一个密集视频字幕生成模型&#xff0c;预测在视频中时间上定位的字幕&#xff0c;理想情况下应该能够处理长的输入视频&#xff0c;预测丰富、…

Linux系统概述与安装

Linux的介绍 Linux内核 Linux内核是 Linux 操作系统主要组件&#xff0c;也是计算机硬件与其软件之间的交互入口。它负责两者之间的通信&#xff0c;还要尽可能高效地管理资源 Linux Shell shell是系统的用户界面&#xff0c;提供了用户与内核进行交互操作的一种接口 Linux文…

java数组.day16(冒泡排序,稀疏数组)

冒泡排序 冒泡排序无疑是最为出名的排序算法之一&#xff0c;总共有八大排序! 冒泡的代码还是相当简单的&#xff0c;两层循环&#xff0c;外层冒泡轮数&#xff0c;里层依次比较&#xff0c;江湖中人人尽皆知。 我们看到嵌套循环&#xff0c;应该立马就可以得出这个算法的时…

2024中国航空航天暨无人机展览会8月在重庆举办

2024中国航空航天暨无人机展览会8月在重庆举办 邀请函 主办单位&#xff1a; 中国航空学会 重庆市南岸区人民政府 招商执行单位&#xff1a; 重庆港华展览有限公司 展会背景&#xff1a; 为更好的培养航空航天产业人才&#xff0c;汇聚航空教育产业创新科技&#xff0c;…

CTK插件框架学习-事件监听(07)

CTK插件框架学习-服务工厂(06)https://mp.csdn.net/mp_blog/creation/editor/137295686 一、简介 事件监听指当事件发生变化时所产生的通信&#xff0c;是动态的&#xff0c;对于已经发生过的事件无法监听 二、事件类型 1、框架事件 监听框架状态变化&#xff0c;因为监听…

usb_camera传输视频流编码的问题记录!

前言&#xff1a; 大家好&#xff0c;今天给大家分享的内容是&#xff0c;一个vip课程付费的朋友&#xff0c;在学习过程中遇到了一个usb采集的视频数据流&#xff0c;经过ffmpeg编码&#xff0c;出现了问题&#xff1a; 问题分析&#xff1a; 其实这个问题不难&#xff0c;关键…

git安装配置教程(小白保姆教程2024最新版)

目录 一、Git是什么?二、安装Git1.下载git2.安装git3.检测git 三、配置Git1.配置本地信息2.配置SSH1&#xff09;SSH与SSH Key是什么&#xff1f;2&#xff09;生成SSH Key3&#xff09;获取ssh key公钥内容&#xff08;id_rsa.pub&#xff09;4&#xff09;Github账号上添加公…