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

二叉树基础oj练习(单值二叉树、相同的树、二叉树的前序遍历)

讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏):

抓紧刷题巩固一下了

目录

1.单值二叉树

题目描述

思路1

代码1

思路2

 代码2

2.相同的树

题目描述 

思路

代码

3.二叉树的前序遍历

代码

 思路


1.单值二叉树

965. 单值二叉树 - 力扣(LeetCode)

题目描述

思路1

利用递归:

首先检查根与左右节点的值是否相等,如果不相等就能直接返回false ,都一样就依次进入左右子树开始检查子树。

对于每个节点,它会检查其左子节点和右子节点的值是否与当前节点的值相同,如果不同则返回 false。如果左右子树都满足条件,则继续递归地检查左子树和右子树

递归的终止条件是当遍历到叶子节点时,此时返回 true

代码1

bool isUnivalTree(struct TreeNode* root) {if(root==NULL)return true;if(root->left!=NULL&&root->left->val!=root->val){return false;}if(root->right!=NULL&&root->right->val!=root->val){return false;}return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

思路2

首先检查根节点是否为空,如果为空则直接返回 true

然后,代码会递归地检查左子树和右子树。对于每个节点,它会检查其左子节点和右子节点的值是否与当前节点的值相同,如果不同则返回 false。同时,它也会递归地检查左子树和右子树是否为unival树(一旦不满足条件,直接返回false)

满足了就走到最后,返回true

 代码2

bool isUnivalTree(struct TreeNode* root) {if(root==NULL)//看根{return true;}if(root->left)//左子树不为空就先看左子树符合否{if(root->left->val!=root->val||!isUnivalTree(root->left))return false;}if(root->right)//右子树不为空{if(root->right->val!=root->val||!isUnivalTree(root->right))return false;}return true;
}

2.相同的树

100. 相同的树 - 力扣(LeetCode)

题目描述 

思路

先根和根比,比完再比左子树和右子树

1. 两者都是空时也相等

2. 左节点或右节点一个存在一个不存在返回false;都存在不相等也是false

3.开始递归,都是NULL时返回true或者返回false停止

代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL&&q==NULL){return true;}if(p==NULL&&q!=NULL){return false;}if(q==NULL&&p!=NULL){return false;}if(p->val!=q->val){return false;}bool left= isSameTree(p->left,q->left);bool right= isSameTree(p->right,q->right);return left&&right;
}


3.二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

代码

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}void preorder(struct TreeNode* root, int* a, int* i)
{if (root == NULL){return;}a[*i] = root->val;(*i)++;preorder(root->left, a, i);preorder(root->right, a, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n = TreeSize(root);*returnSize=n;int* a=(int*)malloc(sizeof(int)*n);int i=0;preorder(root,a,&i);return a;
}

 思路

1.首先题目要求放到malloced的数组里,那就要考虑大小的问题,最后还是运用TreeSize来求一下树里元素的数量比较好,求出来后直接赋值给*returnsize

2.一般使用递归,但是我们已经在函数里面动态开辟了,递归每次调用会消耗很多,最好的办法还是在构建一个函数来进行前置遍历和放入的操作。

3.考虑到参数设置问题,root要有,数组a也要有。那想到需要一个下标才能确保递归时正确放到位置,这个下标还不能在递归函数里面定义,那样没用(都是新的,独立的变量)。

所以要作为参数传入的同时还能保证递归时改变的都是同一个变量那就有两种方法:

  • 全局变量
  • 传入地址:地址虽然也是临时拷贝,但是都是指向同一块区域

相关文章:

二叉树基础oj练习(单值二叉树、相同的树、二叉树的前序遍历)

讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏): 抓紧刷题巩固一下了 目录 1.单值二叉树 题目描述 思路1 代码1 思路2 代码2 2.相同的树 题目描述 思路 代码 3.二叉树的前序遍历 代码 思路 1.单值二叉树 965. 单值二叉树 - 力扣(LeetCod…...

自动化创建ETX用户帐号

在芯片设计行业,ETX是常见的远程访问环境。用户在通过ETX访问远程环境前必须首先加入ETX系统,然后通过profile分配相关的环境的访问权限。 通常这些操作在ETX WEB页面手工操作,如果我们期望实现用户帐号注册全自动化,就需要将以上…...

Android 实现集合去重的方法

方法一&#xff1a;使用HashSet 将集合转换为HashSet。 Set<String> set new HashSet<>(list);将HashSet转换回List。 List<String> uniqueList new ArrayList<>(set);方法二&#xff1a;使用Java 8的Stream API 将列表转换为Stream。 Stream&l…...

【Vue3】2-12 : 【案例】搜索关键词加筛选条件的综合

本书目录&#xff1a;点击进入 一、【案例】搜索关键词加筛选条件的综合 1.1、逻辑 1.2、效果 1.3、json数据 - 02-data.json 1.4、代码 一、【案例】搜索关键词加筛选条件的综合 1.1、逻辑 计算属性 - 绑定list&#xff0c;并过滤 input 双向绑定 - 当input改变时&…...

unity小程序websocket:nginx配置https (wss)转http (ws)及其他问题解决

目录 前言 实际运用场景 处理流程如下 nginx配置ssl和wss 配置过程中遇到的问题 1、无法连接服务器 2、通过IP可以访问&#xff0c;域名却不行 问题描述 解决 3、如何判断该域名是否备案了 前言 为了服务器网络的通用性&#xff0c;我们在实现移动端的游戏转微信小程序…...

MySql数据库对接Orcal数据库,需要考虑的前提问题

1.主表 从表的表关系&#xff1b;主键id 的关联问题&#xff1b; 2.字段类型的一致性问题&#xff08;备注&#xff1a;像varchar类型的一点要谨防数据过长抛错&#xff09;&#xff1b; 3.实体类字段两表一致性问题&#xff1b; 4.入表不为空问题&#xff0c;判空尽量在实体…...

K8S的存储卷---数据卷

容器内的目录和宿主机的目录进行挂载 容器在系统上的生命周期是短暂的。delete&#xff0c;K8S用控制器创建的pod&#xff0c;delete相当于重启&#xff0c;容器的状态也会恢复到初始状态。一旦回到初始状态&#xff0c;所有的后天编辑的文件都会消失 容器和节点之间创建一个…...

【量化交易故事】小明开启了量化创业之旅-01

故事开始于2023年的春天&#xff0c;小明是一位对金融市场充满热情的IT工程师。在经历了数次基于主观判断和个人情绪进行投资却收获平平后&#xff0c;他意识到传统交易方式中的人为因素难以避免&#xff0c;而这往往成为影响投资决策稳定性和准确性的关键障碍。在一次偶然的机…...

ffmpeg写YUV420文件碰到阶梯型横线或者条纹状画面的原因和解决办法

版权声明&#xff1a;本文为CSDN博主「文三~」的原创文章&#xff0c;遵循CC 4.0 BY-SA版权协议&#xff0c;转载请附上原文出处链接及本声明。 原文链接&#xff1a;https://blog.csdn.net/asdasfdgdhh/article/details/112831581 看到了&#xff0c;转载&#xff0c;留着备份…...

案例:新闻数据加载

文章目录 介绍相关概念相关权限约束与限制完整示例 代码结构解读构建主界面数据请求下拉刷新总结 介绍 本篇Codelab是基于ArkTS的声明式开发范式实现的样例&#xff0c;主要介绍了数据请求和touch事件的使用。包含以下功能&#xff1a; 数据请求。列表下拉刷新。列表上拉加载…...

数学的雨伞下:理解世界的乐趣

这本书没有一个公式&#xff0c;却讲透了数学的本质&#xff01; 《数学的雨伞下&#xff1a;理解世界的乐趣》。一本足以刷新观念的好书&#xff0c;从超市到对数再到相对论&#xff0c;娓娓道来。对于思维空间也给出了一个更容易理解的角度。 作者&#xff1a;米卡埃尔•洛奈…...

补充 vue3用户管理权限(路由控制)

之前有人问我 &#xff0c;如果是二级路由如何添加&#xff0c;这里我做一个补充吧。直接拿方法去用就行。也不做解释了。稍微看下就能看懂了 假设&#xff0c;后端返回给我们一个数据 [“/defa”,"/defa/defa1"] 这样的一个路由表&#xff0c;我们就需要通过这个路…...

C++ 深度优先搜索DFS || 模版题:排列数字

给定一个整数 n &#xff0c;将数字 1∼n 排成一排&#xff0c;将会有很多种排列方法。 现在&#xff0c;请你按照字典序将所有的排列方法输出。 输入格式 共一行&#xff0c;包含一个整数 n 。 输出格式 按字典序输出所有排列方案&#xff0c;每个方案占一行。 数据范围 1…...

计算机找不到msvcp120.dll如何解决?总结五个可靠的教程

在计算机使用过程中&#xff0c;遇到“找不到msvcp120.dll”这一问题常常令人困扰。msvcp120.dll作为Windows系统中至关重要的动态链接库文件&#xff0c;对于许多应用程序的正常运行起着不可或缺的作用。那么&#xff0c;究竟是什么原因导致找不到msvcp120.dll呢&#xff1f;又…...

法线变换矩阵的推导

背景 在冯氏光照模型中&#xff0c;其中的漫反射项需要我们对法向量和光线做点乘计算。 从顶点着色器中读入的法向量数据处于模型空间&#xff0c;我们需要将法向量转换到世界空间&#xff0c;然后在世界空间中让法向量和光线做运算。这里便有一个问题&#xff0c;如何将法线…...

React.Children.map 和 js 的 map 有什么区别?

JavaScript 中的 map 不会对为 null 或者 undefined 的数据进行处理&#xff0c;而 React.Children.map 中的 map 可以处理 React.Children 为 null 或者 undefined 的情况。 React 空节点&#xff1a;可以由null、undefined、false、true创建 import React from reactexport …...

13.Kubernetes部署Go应用完整流程:从Dockerfile到Ingress发布完整流程

本文以一个简单的Go应用Demo来演示Kubernetes应用部署的完整流程 1、Dockerfile多阶段构建 Dockerfile多阶段构建 [root@docker github]# git clone https://gitee.com/yxydde/http-dump.git [root@docker github]# cd http-dump/ [root@docker http-dump]# cat Dockerfile …...

叉车车载终端定制_基于MT6762安卓核心板的车载终端设备方案

叉车车载终端是一款专为叉车车载场景设计的4英寸Android车载平板电脑。它采用了高能低耗的8核ARM架构处理器和交互开放的Android 12操作系统&#xff0c;算力表现强大。此外&#xff0c;该产品还具备丰富的Wi-Fi-5、4G LTE和蓝牙等通讯功能&#xff0c;可选配外部车载蘑菇天线&…...

【CSS】保持元素宽高比

保持元素的宽高比&#xff0c;在视频或图片展示类页面是一个重要功能。 本文介绍其常规的实现方法。 实现效果 当浏览器视口发生变化时&#xff0c;元素的尺寸随之变化&#xff0c;且宽高比不变。 代码实现 我们用最简单的元素结构来演示&#xff0c;实现宽高比为4&#xf…...

使用 Docker 和 Diffusers 快速上手 Stable Video Diffusion 图生视频大模型

本篇文章聊聊&#xff0c;如何快速上手 Stable Video Diffusion (SVD) 图生视频大模型。 写在前面 月底计划在机器之心的“AI技术论坛”做关于使用开源模型 “Stable Diffusion 模型” 做有趣视频的实战分享。 因为会议分享时间有限&#xff0c;和之前一样&#xff0c;比较简…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...