LeetCode/NowCoder-二叉树OJ练习

励志冰檗:形容在清苦的生活环境中激励自己的意志。💓💓💓

目录

 说在前面

题目一:单值二叉树

题目二:相同的树

题目三:对称二叉树

题目四:二叉树的前序遍历

题目五:另一棵树的子树

题目六:二叉树的构建及遍历

SUMUP结尾


 说在前面

 dear朋友们大家好!💖💖💖我们又见面了,又到了我们数据结构的刷题时间了。我们上次刚学完了二叉树的知识,现在就让我们来练练手~

 👇👇👇

友友们!🎉🎉🎉点击这里进入力扣leetcode学习🎉🎉🎉


​以下是leetcode题库界面:

​​

 👇👇👇

🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
​以下是NowCoder题库界面:

 

题目一:单值二叉树

题目链接:965. 单值二叉树 - 力扣(LeetCode)

题目描述:

题目分析:

思路:对于二叉树的OJ练习我们一定要多利用递归的思想,即将大问题拆成子问题。首先我们考虑,如果树为空,显然也是单值二叉树,返回true;如果节点中的值与它左右子树根节点的值不同,那肯定返回false;如果和它左右子树根节点的值都相同,就递归到左右子树,按照同样的逻辑即可。

代码如下:

/*** 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;if(root->left && root->val != root->left->val || root->right && root->val != root->right->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

 

题目二:相同的树

题目链接:100. 相同的树 - 力扣(LeetCode)

题目描述:

题目分析:

思路:首先,我们需要判断这两棵树是否为空,如果都为空,那么也是相同的树,如果其中有一个为空,另一个不为空,那就不是相同的树;如果第一棵树和第二棵树的值不相等,那肯定不是相同的树;如果它们的值相等,就需要递归到左右子树,如果左右子树都满足,自然最终会回到第一种情况,再将true回归。

 代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(!p && !q)return true;if(!p || !q)return false;return p->val != q->val ? false : isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

 

题目三:对称二叉树

题目链接:101. 对称二叉树 - 力扣(LeetCode)

题目描述:

题目分析:

思路:这道题的思路和题目二有些许类似,题目二是判断两棵树的左右子树是否相同,而这道题是判断你的左子树和我的右子树是否相同即可,也就是我们把二叉树分为root->left和root->right,利用和题目二相同的逻辑就可以了。

代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {if(!p && !q)return true;if(!p || !q)return false;return p->val != q->val ? false : _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left); 
}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root->left, root->right);
}

 

题目四:二叉树的前序遍历

题目链接:144. 二叉树的前序遍历 - 力扣(LeetCode)

题目描述:

题目分析:

思路:我们再上一章二叉树的部分学习过二叉树的前序遍历,但我们之前的前序遍历在遍历过程中的操作是打印节点的值,我们现在的操作是把它存在一个数组arr中。那数组的大小*returnSize是多少呢?显然就是树的节点,所以我们也需要TreeSize函数来计算树的节点。

代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct TreeNode TreeNode;//树的节点个数
int TreeSize(TreeNode* root)
{if(root == NULL)return 0;return TreeSize(root->left) + TreeSize(root->right) + 1;
}//前序遍历
void PrevOrder(TreeNode* root, int* arr, int* pi)
{if(root == NULL)return;arr[(*pi)++] = root->val;PrevOrder(root->left, arr, pi);PrevOrder(root->right, arr, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* arr = (int*)malloc((*returnSize) * sizeof(int));int i = 0;PrevOrder(root, arr, &i);return arr;
}

注意:i作为数组arr的下标,会随着递归的深度而进行改变,所以需要传址调用。

 

题目五:另一棵树的子树

题目链接:572. 另一棵树的子树 - 力扣(LeetCode)

题目描述:

题目分析:

思路:这道题我们首先判断root本身是否为空,如果本身为空,显然subRoot不可能是root的子树。如果root不为空,我们判断root和subRoot是否是相同的树(相同的树也算true),如果是就返回true,如果不是,就递归到它的左右子树即可。所以我们还需要用到题目二中的相关代码。

代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
//判断两棵树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(!p && !q)   return true;if(!p || !q)    return false;return p->val != q->val ? false : isSameTree(p->left, q->left) && isSameTree(p->right, q->right);    
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root == NULL)return false;return isSameTree(root, subRoot) ? true :isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

 

题目六:二叉树的构建及遍历

题目链接:二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目描述:

题目分析:

思路:这道题依旧用到了我们上一章中前序和中序遍历的思想,首先构建二叉树我们需要将前序遍历存放在数组arr中,用i作为下标。和题目五类似,i也需要传地址调用。

代码如下:

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//二叉树的构建
BTNode* CreateTree(char* arr, int* pi)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if(arr[*pi] == '#'){(*pi)++;return NULL;}root->data = arr[(*pi)++];root->left = CreateTree(arr, pi);root->right = CreateTree(arr, pi);return root;
}//中序遍历
void InOrder(BTNode* root)
{if(root == NULL)return;InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}int main()
{char arr[MAXSIZE];scanf("%s",arr);int i = 0;BTNode* root = CreateTree(arr, &i);InOrder(root);return 0;
}

 

SUMUP结尾

数据结构就像数学题,需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题,希望大家一起学习,共同进步~

如果大家觉得有帮助,麻烦大家点点赞,如果有错误的地方也欢迎大家指出~

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

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

相关文章

秋招突击——7/24——知识补充——JVM类加载机制

文章目录 引言类加载机制知识点复习类的生命周期1、加载2、连接——验证3、连接——准备4、连接——解析5、初始化 类加载器和类加载机制类加载器类加载机制——双亲委派模型 面试题整理1、类加载是什么2、类加载的过程是什么3、有哪些类加载器&#xff1f;4、双亲委派模型是什…

java面向对象进阶进阶篇--《JDK8,JDK9接口中新增的方法、接口的应用、适配器设计模式》

个人主页→VON 收录专栏→java从入门到起飞 接口→接口和接口与抽象类综合案例 一、JDK8接口中新增的方法 在JDK 8中&#xff0c;接口新增了几个重要的特性和方法&#xff0c;其中最显著的是默认方法&#xff08;Default Methods&#xff09;和静态方法&#xff08;Static Met…

Linux嵌入式学习——数据结构——线性表的链式结构

线性表的链式存储 解决顺序存储的缺点&#xff0c;插入和删除&#xff0c;动态存储问题。 特点&#xff1a; 线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素&#xff0c;存储单元可以是连续的&#xff0c;也可以不连续。可以被存储在任意内存未被占…

使用lotusscript控制台吧!

大家好&#xff0c;才是真的好。 我们的公众号通常会涉及到很多lotusScript代码功能&#xff0c;写lotusScript代码时&#xff0c;我常常在想&#xff0c;这行语句明明是对的&#xff0c;为什么会有报错&#xff1f; 为此&#xff0c;常常会在语句中加入on error goto语句&am…

【Git多人协作开发】不同的分支下的多人协作开发模式

目录 0.前言背景 1.开发者1☞完成准备工作&协作开发 1.1查看分支情况 1.2创建本地分支feature-1 1.3三板斧 1.4push推本地分支feature-1到远程仓库 2.开发者2☞完成准备工作&协作开发 2.1创建本地分支feature-2 2.2三板斧 2.2push推送本地feature-2到远程仓库…

黑马JavaWeb企业级开发(知识清单)01——前端介绍,HTML实现标题:排版

文章目录 前言一、认识web前端、HTML、CSS二、VS Code开发工具&#xff08;插件弃用问题&#xff09;三、HTML结构标签介绍1. 标签页标题< title >2. 图片标签< img >1) 常见属性2) src路径书写方式 3. 标题标签< h >4. 水平分页线标签< hr > 四、用Vs…

生成树协议配置与分析

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 一、相关知识 1、生成树协议简介 生成树协议&#xff08;STP&#xff09;是一种避免数据链路层逻辑环路的机制&#xff0c;它通过信息交互识别环路并…

ZLMRTCClient配置说明与用法(含示例)

webRTC播放视频 后面在项目中会用到通过推拉播放视频流的技术&#xff0c;所以最近预研了一下webRTC 首先需要引入封装好的webRTC客户端的js文件ZLMRTCClient.js 下面是地址需要的自行下载 http://my.zsyou.top/2024/ZLMRTCClient.js 配置说明 new ZLMRTCClient.Endpoint…

AI/机器学习(计算机视觉/NLP)方向面试复习2

1. 用pytorch写一个self-attention 继承pytorch.nn.Module的类 代码&#xff1a; import torch import torch.nn as nn import torch.nn.functional as Fclass SelfAttention(nn.Module):def __init__(self, embed_size): # (B,T,C)super(SelfAttention, self).__init__()sel…

如何优化 Selenium 和 BeautifulSoup 的集成以提高数据抓取的效率?

摘要 在互联网时代&#xff0c;数据的价值日益凸显。对于电商网站如京东&#xff0c;其商品信息、用户评价等数据对于市场分析、产品定位等具有重要意义。然而&#xff0c;由于这些网站通常使用 JavaScript 动态生成内容&#xff0c;传统的爬虫技术难以直接获取到完整数据。本…

手机空号过滤批量查询的意义及方法

手机空号过滤批量查询是现代营销和通信管理中常用的技术手段&#xff0c;旨在通过批量处理手机号码&#xff0c;筛选出活跃号码和空号等无效号码&#xff0c;以提高营销效率和减少不必要的通信成本。以下是关于手机空号过滤批量查询的详细解答&#xff1a; 一、手机空号过滤批…

逆向笔记-某贴

逆向环境搭建 雷电模拟器9LsposedMagisk DeltaMTNP管理器算法助手2.1.2 软件链接&#xff1a; https://llzai.lanzouv.com/iWgV125h6vwj 密码:a0zy 主要注释代码 捕获窗口&#xff0c;查看日志&#xff0c;定位代码 找到show的里面的alertdialog的相关行都注释掉就好了&am…

HTML5-canvas1

1、canvas&#xff1a;创建画布 <canvas id"canvas"></canvas>2、画一条直线 var canvasdocument.getElementById(cancas&#xff09;; canvas.width800; canvas.height800; var contextcanvas.getContext(2d); //获得2d绘图上下文环境 //画一条直线 c…

全新AI工具——PaintsUndo:一键自动还原图像绘画过程!

ControlNet 作者 Lvmin Zhang 又开始整活了&#xff01;这次发布的PaintsUndo 只需要上传一张图片&#xff0c; 就能够一键生成绘画过程&#xff01;快来了解学习&#xff01; 1、核心技术 PaintsUndo 是一项突破性的技术&#xff0c;旨在通过输入静态图像&#xff0c;自动生…

基于vue-grid-layout插件(vue版本)实现增删改查/拖拽自动排序等功能(已验证、可正常运行)

前端时间有个需求&#xff0c;需要对33&#xff08;不一定&#xff0c;也可能多行&#xff09;的卡片布局&#xff0c;进行拖拽&#xff0c;拖拽过程中自动排序&#xff0c;以下代码是基于vue2&#xff0c;可直接运行&#xff0c;报错可评论滴我 部分代码优化来自于GPT4o和Clau…

Live555源码阅读笔记:哈希表的实现

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

Air780EP模块 LuatOS开发-MQTT接入阿里云应用指南

简介 本文简单讲述了利用LuatOS-Air进行二次开发&#xff0c;采用一型一密、一机一密两种方式认证方式连接阿里云。整体结构如图 关联文档和使用工具&#xff1a;LuatOS库阿里云平台 准备工作 Air780EP_全IO开发板一套&#xff0c;包括天线SIM卡&#xff0c;USB线 PC电脑&…

【时时三省】unity test 测试框架 下载

目录 1&#xff0c;unity test 测试框架介绍 2&#xff0c;源码下载 3&#xff0c;目录架构 4&#xff0c;git for window 下载安装方法&#xff1a; 1&#xff0c;unity test 测试框架介绍 Unity是一个用于C语言的轻量级单元测试框架。它由Throw The Switch团队开发&#…

LINUX客户端client(socket、connect,write)实现客户端发送,服务器接收

SERVICE端见前一篇文章 5. 客户端连接函数 connect()&#xff08;与前面的bind一样&#xff09; int connect (int sockfd, struct sockaddr * serv_addr, int addrlen) 参数&#xff1a; sockfd: 通过 socket() 函数拿到的 fd addr:struct sockaddr 的结构体变量地址 addr…

深入指南:VitePress 如何自定义样式

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…