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

二叉树经典14题——初学二叉树必会的简单题

此篇皆为leetcode、牛客中的简单题型和二叉树基础操作,无需做过多讲解,仅付最优解。有需要的小伙伴直接私信我~

目录

1.二叉树的节点个数

2.二叉树叶子节点个数

3.二叉树第K层节点个数

4.查找值为X的节点

5.leetcode——二叉树的最大深度

6.leetcode——单值二叉树

7.leetcode——相同的树

8.二叉树的前序遍历

9.二叉树的中序遍历 

10.二叉树的后序遍历 

11.二叉树的层序遍历

12.leetcode——另一棵树的子树

13.二叉树的构建及遍历 

14.leetcode——对称二叉树


1.二叉树的节点个数

int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

2.二叉树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3.二叉树第K层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

4.查找值为X的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType data)
{if (root == NULL)return NULL;if (root->data == data)return root;BTNode* ret1 = BinaryTreeFind(root->left, data);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->right, data);if (ret2)return ret2;return NULL;
}

5.leetcode——二叉树的最大深度

oj链接:二叉树的最大深度

int maxDepth(struct TreeNode* root) {if (root == NULL)return 0;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return  (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

6.leetcode——单值二叉树

oj链接:单值二叉树

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

7.leetcode——相同的树

oj链接:相同的树

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

8.二叉树的前序遍历

详细讲解:二叉树的前、中、后序遍历

void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);//前序在前PrevOrder(root->left);PrevOrder(root->right);
}

9.二叉树的中序遍历 

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);//中序在中InOrder(root->right);
}

10.二叉树的后序遍历 

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);//后序在后
}

11.二叉树的层序遍历

详细讲解:看完这篇我不信你不会二叉树的层序遍历

//需自己实现队列的数据结构
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);elsereturn;while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if(front->left)QueuePush(&q, front->left);if(front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);
}

12.leetcode——另一棵树的子树

oj链接:另一棵树的子树

//判断两树是否相同(复用“相同的树”解题代码)
bool isSametree(struct TreeNode* p,struct TreeNode* q)
{if(p==NULL && q==NULL)return true;if(p==NULL || q==NULL)return false;if(p->val != q->val)return false;return isSametree(p->left,q->left) && isSametree(p->right,q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root==NULL)return false;if(isSametree(root,subRoot))return true;return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

13.二叉树的构建及遍历 

题目链接:二叉树的遍历

注意:本题虽然是二叉树的遍历,但考查的却是如何通过数组的内容构建一棵二叉树。

#include <stdio.h>
#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};struct TreeNode* rebuildTree(char* str,int* pi)
{if(str[*pi] == '#'){(*pi)++;return NULL;}struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = str[(*pi)++];root->left = rebuildTree(str,pi);root->right = rebuildTree(str,pi);return root;
}void TreeDestory(struct TreeNode* root)
{if(root==NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}void InOrder(struct TreeNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}
int main() {char str[100];scanf("%s",str);int i=0;struct TreeNode* root = rebuildTree(str,&i);InOrder(root);TreeDestory(root);return 0;
}

14.leetcode——对称二叉树

oj链接:对称二叉树

bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL)return true;if (p == NULL || q == NULL)return false;if (p->val != q->val)return false;return _isSymmetric(p->left, q->right) &&_isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {return root == NULL ? 0 : _isSymmetric(root->left, root->right);
}

相关文章:

二叉树经典14题——初学二叉树必会的简单题

此篇皆为leetcode、牛客中的简单题型和二叉树基础操作&#xff0c;无需做过多讲解&#xff0c;仅付最优解。有需要的小伙伴直接私信我~ 目录 1.二叉树的节点个数 2.二叉树叶子节点个数 3.二叉树第K层节点个数 4.查找值为X的节点 5.leetcode——二叉树的最大深度 6.leetc…...

基于NMOSFET的电平转换电路设计

一、概述&#xff1a; 在单片机系统中&#xff0c;5V、3.3V是芯片常用的电平。而在传输协议中(如IIC、SPI等协议)&#xff0c;存在芯片与芯片的高电平和低电平定义的范围不一样&#xff0c;所以需要存在一个电平转换电路&#xff0c;来使芯片与芯片之间顺利的传输。 二、前置…...

mongoDB搭建集群

(学习自黑马)下载对应linux版本MongoDB源码下载地址&#xff1a;https://www.mongodb.com/download-center#community目前在一台服务器开三个端口模拟三个mongodb, 配置一个主节点27017,一个从节点27018,一个仲裁者27019配置主节点,副节点,仲裁节点(下面的创建文件一共有三份,通…...

[深入理解SSD系列 闪存2.1.5] NAND FLASH基本读操作及原理_NAND FLASH Read Operation源码实现

前言 上面是我使用的NAND FLASH的硬件原理图,面对这些引脚,很难明白他们是什么含义, 下面先来个热身: 问1. 原理图上NAND FLASH只有数据线,怎么传输地址? 答1.在DATA0~DATA7上既传输数据,又传输地址 当ALE为高电平时传输的是地址, 问2. 从NAND FLASH芯片手册可知,要…...

最新 JVM 面试经典问题

文章目录 说说JVM的内存布局?知道new一个对象的过程吗?知道双亲委派模型吗?说说有哪些垃圾回收算法?标记-清除复制算法标记-整理那么什么是GC ROOT?有哪些GC ROOT?垃圾回收器了解吗?年轻代和老年代都有哪些垃圾回收器?G1的原理了解吗?什么时候会触发YGC和FGC?对象什么…...

HTML5 和 CSS3 的新特性

目标能够说出 3~5 个 HTML5 新增布局和表单标签能够说出 CSS3 的新增特性有哪些HTML5新特性概述HTML5 的新增特性主要是针对于以前的不足&#xff0c;增加了一些新的标签、新的表单和新的表单属性等。 这些新特性都有兼容性问题&#xff0c;基本是 IE9 以上版本的浏览器才支持&…...

Vulnhub系列:FristLeaks

一、配置靶机环境以往的靶机&#xff0c;本人是在virtual box中&#xff0c;去配置&#xff0c;和vm上的kali进行联动&#xff0c;但是这个靶机需要DHCP&#xff0c;以往的方式可能不太行了&#xff0c;或者可以在virtual box中桥接成统一网卡。下面介绍下本人最有用的方法&…...

XWiki Annotation Displayer 存在任意代码执行漏洞(CVE-2023-26475)

漏洞描述 XWiki 是一个开源的企业级 Wiki 平台&#xff0c;Annotation Displayer 是 XWiki 中的一个插件&#xff0c;用于在 XWiki 页面上显示注释和其他相关内容。 该项目受影响版本存在任意代码执行漏洞&#xff0c;由于Annotation Displayer 对 Groovy 宏的使用没有限制&a…...

数字孪生GIS智慧风场Web3D可视化运维系统

随着国家双碳目标的实施&#xff0c;新能源发电方式逐渐代替了污染大气层的火力发电&#xff0c;其中风力发电相比于光伏发电具有能量密度高、发电小时数长、生命周期达20-25年之久等独特的优势。风能取之不尽、用之不竭&#xff0c;在新型能源互联网下&#xff0c;风力发电有可…...

Retrofit核心源码分析(二)- 网络请求和响应处理

在上一篇文章中&#xff0c;我们详细分析了 Retrofit 中的注解解析和动态代理实现&#xff0c;本篇文章将继续深入研究 Retrofit 的核心源码&#xff0c;重点分析 Retrofit 如何进行网络请求和响应处理。 网络请求 在使用 Retrofit 发起网络请求时&#xff0c;我们可以通过定…...

STM32启动模式讲解与ICP下载电路

一、官方提供的启动模式说明硬件BOOT引脚接法表格从表格可以看出有三种启动模式&#xff0c;然后对应这不同的存储器启动&#xff0c;那我们现在疑问为啥有三种不能只有一种就好&#xff0c;还有存储器启动区域怎么区分&#xff0c;有些乱&#xff0c;带着这些疑问&#xff0c;…...

5款小巧好用的电脑软件,让你的工作生活更加高效!

不得不说良心好软件让大家好评连连&#xff0c;爱不释手&#xff0c;不像某些软件自带广告弹窗。这期就由我给大家安利几款电脑中的得力助手&#xff0c;看看你都用过几个&#xff1f; 1.桌面管理神器——Coodesker Coodesker是一款免费小巧、无广告&#xff0c;功能简单的桌…...

python线程池

假设我们必须多线程任务创建大量线程。 由于线程太多&#xff0c;因此可能会有很多性能问题&#xff0c;这在计算上会是最昂贵的。 一个主要问题可能是吞吐量受限。 我们可以通过创建一个线程池来解决这个问题。 一个线程池可以被定义为一组预先实例化和空闲的线程&#xff0c;…...

深入浅出PaddlePaddle函数——paddle.ones_like

分类目录&#xff1a;《深入浅出PaddlePaddle函数》总目录 相关文章&#xff1a; 深入浅出PaddlePaddle函数——paddle.Tensor 深入浅出PaddlePaddle函数——paddle.ones 深入浅出PaddlePaddle函数——paddle.zeros 深入浅出PaddlePaddle函数——paddle.full 深入浅出Padd…...

计算机组成原理(海明码效验)(3)-软件设计(二十四)

计算机组成原理&#xff08;2&#xff09;-软件设计&#xff08;二十三&#xff09;https://blog.csdn.net/ke1ying/article/details/129394115 一、总线 分为 内部总线、系统总线、外部总线。 内部总线&#xff1a;指芯片级别的总线&#xff0c;连接各个芯片。 系统总线&a…...

Linux2.2网络驱动程序编写

一.Linux系统设备驱动程序概述1.1 Linux设备驱动程序分类1.2 编写驱动程序的一些基本概念二.Linux系统网络设备驱动程序2.1 网络驱动程序的结构2.2 网络驱动程序的基本方法2.3 网络驱动程序中用到的数据结构2.4 常用的系统支持三.编写Linux网络驱动程序中可能遇到的问题3.1 中断…...

像素密度提升33%,Quest Pro动态注视点渲染原理详解

在Connect 2022上&#xff0c;Meta发布了Quest Pro&#xff0c;并首次在VR中引入动态注视点渲染&#xff08;ETFR&#xff09;功能&#xff0c;这是一种新型图形优化技术&#xff0c;特点是以用户注视点为中心&#xff0c;动态调节VR屏幕的清晰度&#xff08;注视点中心最清晰、…...

【Linux实战篇】二、在Linux上部署各类软件

一、实战章节&#xff1a;在Linux上部署各类软件 二、MySQL数据库管理系统安装部署【简单】 简介 MySQL数据库管理系统&#xff08;后续简称MySQL&#xff09;&#xff0c;是一款知名的数据库系统&#xff0c;其特点是&#xff1a;轻量、简单、功能丰富。 MySQL数据库可谓是…...

基于SpringBoot的学生会管理系统 源码

StudentUnionManagementSystem 基于SpringBoot的学生会管理系统 源码 链接 目录StudentUnionManagementSystem介绍软件架构使用说明1.页面登录2.首页3.成员信息管理4.角色信息管理5.权限管理6.活动管理7.文件管理8.活动展示介绍 学生会管理系统 SpringBoot Mybatis-plus shir…...

[league/glide]两行代码实现一套强大的图片处理HTTP服务

只要两行代码&#xff0c;就能实现类似对象存储云提供的基于参数的图片处理&#xff0c;比如裁剪、放大、水印、旋转等等。 我们经常使用第三方的对象存储服务&#xff0c;比如七牛云或阿里云&#xff0c;他们都提供了“智能媒体服务”&#xff0c;其实就是在链接上加上各种参…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

对WWDC 2025 Keynote 内容的预测

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

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...