单值二叉树(C语言详解版)
一、摘要
今天要讲的是leetcode单值二叉树,这里用到的C语言,主要提供的是思路,大家看了我的思路之后可以点击链接自己试一下。
二、题目简介
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true
;否则返回 false
。
示例 1:
输入:[1,1,1,1,1,null,1] 输出:true
示例 2:
输入:[2,2,2,5,2] 输出:false
提示:
- 给定树的节点数范围是
[1, 100]
。 - 每个节点的值都是整数,范围为
[0, 99]
。
三、思路分析
思路一(递归)
当我们看到这道题目时,一个直观的想法是通过递归遍历二叉树来解决问题。在遍历过程中,我们需要将每个节点的值与根节点的值进行比对。如果所有节点的值都与根节点一致,那么返回 true
;否则返回 false
。这种方法与递归实现二叉树的前序、中序或后序遍历有一定的相似性。因此,我们需要注意二叉树的结构特性,确保在遍历过程中,左子树和右子树都被完整地访问到。这是解决这道题的一个常见思路。
接下来,我将通过代码来展示这个思路的实现。
代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool isUnivalTree(struct TreeNode* root) {// 如果当前节点为空,说明已经遍历到叶子节点的子节点,返回 trueif (root == NULL) {return true;}// 检查左子节点是否存在,且其值是否与当前节点的值不同if (root->left && root->left->val != root->val) {return false;}// 检查右子节点是否存在,且其值是否与当前节点的值不同if (root->right && root->right->val != root->val) {return false;}// 递归检查左子树和右子树return isUnivalTree(root->left) && isUnivalTree(root->right);
}
大家可以代入一个中途不相同值的二叉树,进行递归展开,这个递归比较简单很好理解。
思路二(迭代)
递归方法虽然简洁,但在某些情况下可能会受到递归深度的限制(尤其是对于非常深的二叉树)。我们可以使用迭代法来避免递归的开销。
-
使用一个队列来存储待访问的节点。
-
从根节点开始,将根节点的值作为目标值。
-
遍历队列中的每个节点,检查其值是否与目标值一致。
-
如果发现任意一个节点的值与目标值不同,直接返回
false
。 -
如果所有节点都通过检查,最终返回
true
。
代码实现:
#include <stdbool.h>
#include <stdlib.h>/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool isUnivalTree(struct TreeNode* root) {if (root == NULL) return true; // 空树是单值二叉树int target = root->val; // 目标值为根节点的值struct TreeNode* queue[100]; // 队列,假设最多100个节点int front = 0, rear = 0;queue[rear++] = root; // 将根节点加入队列while (front < rear) {struct TreeNode* node = queue[front++]; // 出队if (node->val != target) return false; // 如果当前节点值与目标值不同,直接返回false// 将左右子节点加入队列(如果存在)if (node->left) queue[rear++] = node->left;if (node->right) queue[rear++] = node->right;}return true; // 所有节点都通过检查,返回true
}
代码解释:
-
队列初始化:
-
使用一个数组
queue
作为队列,存储待访问的节点。 -
使用两个指针
front
和rear
分别表示队列的头部和尾部。
-
-
目标值:
-
将根节点的值作为目标值
target
,所有节点的值都需要与它一致。
-
-
层次遍历:
-
从根节点开始,将其加入队列。
-
每次从队列中取出一个节点,检查其值是否与目标值一致。
-
如果一致,将其左右子节点(如果存在)加入队列。
-
如果发现任意一个节点的值与目标值不同,直接返回
false
。
-
-
结束条件:
-
如果队列为空,说明所有节点都已检查完毕,返回
true
。
-
优点:
-
避免递归:使用迭代法避免了递归的深度限制问题。
-
逻辑清晰:层次遍历的逻辑直观,容易理解和实现。
-
高效:时间复杂度为 O(n),其中 n 是树的节点数。
其实这道题思路和内容都挺简单的,这道题还可以通过全局变量记录目标值,或者DFS来实现,我们在日常学习过程中都可以通过一题多解的方法来锻炼代码思考能力。好啦今天的leetcode每日一题就到这里啦!
相关文章:

单值二叉树(C语言详解版)
一、摘要 今天要讲的是leetcode单值二叉树,这里用到的C语言,主要提供的是思路,大家看了我的思路之后可以点击链接自己试一下。 二、题目简介 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单…...

python学opencv|读取图像(四十二)使用cv2.add()函数实现多图像叠加
【1】引言 前序学习过程中,掌握了灰度图像和彩色图像的掩模操作: python学opencv|读取图像(九)用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 python学opencv|读取图像(四十)掩模:三…...

速通Docker === Docker Compose
目录 Docker Compose 简介 Docker Compose 常用命令 使用 Docker Compose 启动 WordPress 普通启动方式(使用 Docker 命令) 使用 Docker Compose 启动 Docker Compose 的特性 Docker Compose 简介 Docker Compose 是一个用于定义和运行多容器 Dock…...

LMI Gocator GO_SDK VS2019引用配置
LMI SDK在VS2019中的引用是真的坑爹,总结一下经验,希望后来的人能少走弯路.大致内容如下: (1) 环境变量 (2)C/C 附加包含目录 E:\GWQ\Gocator\GO_SDK\Gocator\GoSdk E:\GWQ\Gocator\GO_SDK\Platform\kApi (3&#…...
技术之翼,创作之心
引言:初入编程的迷茫与追求 当我第一次接触到编程时,心中充满了既期待又迷茫的情感。那时,我还是一名刚刚踏入大学的学生,面对一门陌生而复杂的学科——计算机科学,我的内心充满了好奇与困惑。课堂上,老师…...
WebSocket异步导出
WebSocket异步导出 1、安装sockjs-client和stompjs2、连接后台3、vite.config.ts 配置反向代理4、导出并实时通信5、 封装WebSocket 文件注册登录(城通网盘) 1、安装sockjs-client和stompjs import SockJS from sockjs-client/dist/sockjs.min.js import Stomp from stompjs2、…...

OS2.【Linux】基本命令入门(1)
目录 1.操作系统是什么? 2.好操作系统的衡量标准 3.操作系统的核心工作 4.在计算机上所有行为都会被转换为硬件行为 5.文件 6.简单介绍一些基本命令 1.clear 2.pwd 3.ls 1.ls -l 2.隐藏文件的创建 3.ls -al 4.ls -ld 5.ls -F(注意是大写) 4.cd 1.cd .. "…...

【二叉树】4. 判断一颗二叉树是否是平衡二叉树。5. 对称二叉树。6. 二叉树的构建及遍历 7. 二叉树的分层遍历 。
判断一颗二叉树是否是平衡二叉树。OJ链接 可以在求树高度的过程中判断树是否平衡 对称二叉树。OJ链接 二叉树的构建及遍历。OJ链接 注意:public static int i最好把static去掉 否则当有多个测试用例时 i无法重新为0二叉树的分层遍历 。OJ链接 但此题要求返回List…...

OS Copilot功能测评:智能助手的炫彩魔法
简介: OS Copilot 是一款融合了人工智能技术的智能助手,专为Linux系统设计,旨在提升系统管理和运维效率。本文详细介绍了在阿里云ECS实例上安装和体验OS Copilot的过程,重点评测了其三个核心参数:-t(模式…...

MFC结构体数据文件读写实例
程序功能将结构体内数组数据写入文件和读出 2Dlg.h中代码: typedef struct Student {int nNum[1000];float fScore;CString sss;}stu; class CMy2Dlg : public CDialog { // Construction public:CMy2Dlg(CWnd* pParent NULL); // standard constructorstu stu1; ... } 2Dl…...
音频 PCM 格式 - raw data
文章目录 raw 音频格式:PCM其他音频格式:mp31. 无损压缩音频(类比 PNG 图像)2. 有损压缩音频(类比 JPEG 图像) 试了一下科大讯飞的音频识别云 api,踩了点坑 与本文无关:讯飞的 api 使…...
关于deepin上运行Qt开发的程序
国产化替代是将来各单位的主流趋势,探索自行开发应用程序在国产操作系统上正常运行是将来的主要工作之一。本文浅尝gui程序在统信社区版——deepin上遇到的小问题。 使用Qt在deepin上做了一个类似gif的帧动画弹窗,在编译运行时,程序可以正常…...

css 如何将字体进行压扁,即水平缩放scaleX
1、下面是来自baidu ai的结果: 2、下面是测试结果: .font-yh {text-align: center;font-family: msyh;display: inline-block; /* 确保transform作用于元素本身 */transform: scaleX(1.5); /* 水平缩放 */ } font-face {font-family: msyh;font-style:…...

C++AVL树(二)详解
文章目录 AVL树旋转单旋右单旋左单旋 双旋左右双旋右左双旋 平衡因子的更新左右双旋右左双旋 判断是不是AVL树时间复杂度分析全部的代码 AVL树 旋转 单旋 单旋是纯粹的一边高 单旋平衡因子是同号 右单旋 a,b,c自身不能发生旋转 并且也不能不向上继续更新(不能停…...
RocketMQ 的 Topic 和消息队列MessageQueue信息,是怎么分布到Broker的?怎么负载均衡到Broker的?
目录 1. Topic 和 MessageQueue 的基本概念 1.1 Topic 1.2 MessageQueue 2. Topic 和 MessageQueue 的分布 2.1 Topic 的创建 2.2 MessageQueue 分配到 Broker 2.3 分布规则 3. 负载均衡机制 3.1 Producer 的负载均衡 3.2 Consumer 的负载均衡 3.3 Broker 的负载均衡…...
无人机核心项目开发系列:从设计到实现的完整解析
无人机核心项目开发系列:从设计到实现的完整解析 01-面试大保健-核心项目-无人机-架构-硬件 1. 无人机项目概述 在这篇博客中,我们将回顾一个遥控四轴无人机的项目。这是一个面向儿童的玩具无人机,具备基础的飞行功能:上升、下…...

浅谈Redis
2007 年,一位程序员和朋友一起创建了一个网站。为了解决这个网站的负载问题,他自己定制了一个数据库。于2009 年开发,称之为Redis。这位意大利程序员是萨尔瓦托勒桑菲利波(Salvatore Sanfilippo),他被称为Redis之父,更…...

Ceisum无人机巡检直播视频投射
接上次的视频投影,Leader告诉我这个视频投影要用在两个地方,一个是我原先写的轨迹回放那里,另一个在无人机起飞后的地图回显,要实时播放无人机拍摄的视频,还要能转镜头,让我把这个也接一下。 我的天&#x…...

【组件库】使用Vue2+AntV X6+ElementUI 实现拖拽配置自定义vue节点
先来看看实现效果: 【组件库】使用 AntV X6 ElementUI 实现拖拽配置自定义 Vue 节点 在现代前端开发中,流程图和可视化编辑器的需求日益增加。AntV X6 是一个强大的图形化框架,支持丰富的图形操作和自定义功能。结合 ElementUI,…...
Vue.js组件开发-如何实现全选反选
在 Vue.js 中实现全选和反选功能,可以通过结合v-model、计算属性和事件处理来完成。 实现思路 • 数据绑定:为每个复选框绑定一个选中状态。 • 全选控制:通过一个复选框控制所有复选框的选中状态。 • 反选控制:通过一个按钮或…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...

MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...