二叉树经典OJ练习
个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创二叉树经典OJ练习
收录于专栏【数据结构初阶】
本专栏旨在分享学习数据结构学习的一点学习笔记,欢迎大家在评论区交流讨论💌
目录
前置说明
1. 单值二叉树
2. 相同的树
3. 对称二叉树
4. 二叉树的前序遍历
5. 二叉树中序遍历
6. 二叉树的后序遍历
7. 另一颗树的子树
前置说明
这里大家需要有二叉树的一些基础,还不是很了解的宝子们可以点击下方链接进行查看
---数据结构之二叉树的超详细讲解(3)--(二叉树的遍历和操作)-CSDN博客
1. 单值二叉树
Oj链接--965. 单值二叉树 - 力扣(LeetCode)
题目描述:
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true
;否则返回 false
。
示例 1:
输入:[1,1,1,1,1,null,1] 输出:true
示例 2:
输入:[2,2,2,5,2] 输出:false
提示:
- 给定树的节点数范围是
[1, 100]
。 - 每个节点的值都是整数,范围为
[0, 99]
。
分析:
题目中给定树的节点数范围是
[1, 100],这里我们就不需要额外判断空节点的情况,我们只需要对二叉树进行遍历一遍,如果遇到空节点返回true,如果root左节点或右节点val不等于root->val,返回false,将最后的结果上传,即可得到最终的结果.
代码展示:
bool isUnivalTree(struct TreeNode* root) {if(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);
}
核心逻辑
空树检查
if(root == NULL) return true;
这里首先检查根节点是否为空。如果根节点为空,则该树被认为是单值二叉树,返回
true
。左子节点值检查
if(root->left && root->left->val != root->val) return false;
接下来检查左子节点。如果左子节点存在且其值与根节点的值不相同,则该树不是单值二叉树,返回
false
。右子节点值检查
if(root->right && root->right->val != root->val) return false;
同样地,检查右子节点。如果右子节点存在且其值与根节点的值不相同,则该树不是单值二叉树,返回
false
。递归检查子树
return isUnivalTree(root->left) && isUnivalTree(root->right);
如果当前节点及其直接子节点都满足条件,则递归检查左子树和右子树。只有在左右子树都是单值二叉树的情况下,当前树才是单值二叉树。
总结
该函数通过递归检查每个节点及其子节点的值是否与根节点的值相同来判断整个二叉树是否是单值二叉树。如果某个节点的值与其父节点不同,立即返回
false
。否则,继续递归检查其子树,最终返回整个树的结果。
2. 相同的树
OJ链接--100. 相同的树 - 力扣(LeetCode)
题目描述:
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3] 输出:true
示例 2:
输入:p = [1,2], q = [1,null,2] 输出:false
示例 3:
输入:p = [1,2,1], q = [1,1,2] 输出:false
提示:
- 两棵树上的节点数目都在范围
[0, 100]
内 -104 <= Node.val <= 104
分析:
两棵树上的节点数目都在范围
[0, 100]
内,说明这里需要进行空树的判断,我们需要先进行判断,当两棵树节点都为空时,满足条件,返回true.当两个节点只有一个为空时,不满足条件,返回false.当两个节点都不为空时,比较两个节点的val,不相等返回false.然后递归遍历两棵树.
代码展示:
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);
}
- 首先检查
p
和q
是否同时为NULL
,如果是,说明两棵树都为空,返回true
。- 然后检查
p
和q
是否其中一个为NULL
,另一个不是。如果是,说明两棵树中的节点个数不同,返回false
。- 接着检查
p
和q
的当前节点值是否相同,如果不同,返回false
。- 最后,通过递归调用
isSameTree
函数比较两棵树的左子树和右子树是否相同,如果均相同则返回true
,否则返回false
。这段代码非常简洁而且有效地比较了两棵树是否相同。它利用了递归的特性,逐层比较树的节点值以及对应的子树,从而判断两棵树是否相同。
3. 对称二叉树
OJ链接--101. 对称二叉树 - 力扣(LeetCode)
题目描述:
给你一个二叉树的根节点 root
, 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3] 输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3] 输出:false
提示:
- 树中节点数目在范围
[1, 1000]
内 -100 <= Node.val <= 100
代码展示:
bool check(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 check(p->left, q->right) && check(p->right, q->left);elsereturn false;
}bool isSymmetric(struct TreeNode* root) {return check(root, root);
}
分析:
check
函数:
- 首先检查
p
和q
是否同时为NULL
,如果是,说明两个节点都为空,返回true
。- 然后检查
p
和q
是否其中一个为NULL
,另一个不是。如果是,说明两个节点中的一个为空,另一个不为空,返回false
。- 接着检查
p
和q
的值是否相等,如果相等,则递归地比较p
的左子树和q
的右子树,以及p
的右子树和q
的左子树是否对称。如果均对称,则返回true
,否则返回false
。
isSymmetric
函数:
- 调用
check
函数,并传入根节点的左右子树作为参数进行比较。这段代码利用递归的方式判断了一棵二叉树是否对称。它通过比较树的左右子树是否镜像对称来判断整棵树是否对称。整体上,这段代码实现了一个简洁而有效的对称性判断算法。
函数递归展开图:
4. 二叉树的前序遍历
OJ链接--144. 二叉树的前序遍历 - 力扣(LeetCode)
题目描述:
给你二叉树的根节点 root
,返回它节点值的 前序 遍历。
示例 1:
输入:root = [1,null,2,3] 输出:[1,2,3]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
示例 4:
输入:root = [1,2] 输出:[1,2]
示例 5:
输入:root = [1,null,2] 输出:[1,2]
提示:
- 树中节点数目在范围
[0, 100]
内 -100 <= Node.val <= 100
分析:
注意这道题目的要求:
/**
* 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().
*/
int* preorderTraversal(struct TreeNode* root, int* returnSize) {}
这里我们需要返回的是前序遍历好的数组,而且需要我们自己malloc创建.函数的参数一个是根节点一个是节点个数,要我们实现的是一个输出型函数.
代码展示:
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void preOrder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;a[(*pi)++] = root->val;preOrder(root->left, a, pi);preOrder(root->right, a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;preOrder(root, a, &i);return a;
}
这段代码是关于二叉树前序遍历的实现,其中包括了计算二叉树节点总数和返回前序遍历结果的功能。让我们对这段代码进行详细分析:
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; }
这部分代码是计算二叉树节点总数的函数
TreeSize
,使用了递归的方式来统计节点数量。在每个节点上,它会递归地调用自身来计算左子树和右子树的节点数,并加上当前节点。void preOrder(struct TreeNode* root, int* a, int* pi) { if(root == NULL) return; a[(*pi)++] = root->val; preOrder(root->left, a, pi); preOrder(root->right, a, pi); }
这部分代码是实现前序遍历的函数
preOrder
,它将遍历得到的节点值存储在数组a
中,使用指针pi
来跟踪数组的索引位置。int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root); int* a = (int*)malloc(sizeof(int)*(*returnSize)); int i = 0; preOrder(root, a, &i); return a; }
最后,
preorderTraversal
函数整合了前两部分的功能。它先计算二叉树的节点总数,然后动态分配一个数组a
来存储前序遍历的结果,并调用preOrder
函数来填充数组。最终将数组返回。总结
这段代码实现了计算二叉树节点总数并返回其前序遍历结果的功能。通过递归的方式遍历二叉树,将节点值按前序遍历顺序存储在数组中,并返回该数组。这样的实现使得我们能够方便地获取二叉树的前序遍历结果,并且能够有效地处理动态分配内存以存储结果。
5. 二叉树中序遍历
OJ链接--94. 二叉树的中序遍历 - 力扣(LeetCode)
题目描述:
给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[1,3,2]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
提示:
- 树中节点数目在范围
[0, 100]
内 -100 <= Node.val <= 100
后面的中序和后序跟前序相差不大,这里就不过多解释.
代码展示:
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void inOrder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL){return;}inOrder(root->left,a,pi);a[(*pi)++] = root->val;inOrder(root->right,a,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;inOrder(root,a,&i);return a;
}
6. 二叉树的后序遍历
OJ链接--145. 二叉树的后序遍历 - 力扣(LeetCode)
题目描述:
给你一棵二叉树的根节点 root
,返回其节点值的 后序遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[3,2,1]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
提示:
- 树中节点的数目在范围
[0, 100]
内 -100 <= Node.val <= 100
代码展示:
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void postOrder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;postOrder(root->left, a, pi);postOrder(root->right, a, pi);a[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;postOrder(root, a, &i);return a;
}
7. 另一颗树的子树
OJ链接--572. 另一棵树的子树 - 力扣(LeetCode)
题目描述:
给你两棵二叉树 root
和 subRoot
。检验 root
中是否包含和 subRoot
具有相同结构和节点值的子树。如果存在,返回 true
;否则,返回 false
。
二叉树 tree
的一棵子树包括 tree
的某个节点和这个节点的所有后代节点。tree
也可以看做它自身的一棵子树。
示例 1:
输入:root = [3,4,5,1,2], subRoot = [4,1,2] 输出:true
示例 2:
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出:false
提示:
root
树上的节点数量范围是[1, 2000]
subRoot
树上的节点数量范围是[1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104
分析:
遍历root树,找到root的所有子树与subroot树进行比较
代码展示:
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(root->val == subRoot->val && isSameTree(root, subRoot))return true;return isSubtree(root->left,subRoot) || isSubtree(root->right, subRoot);
}
注意:这里需要用到我们之前已经解决的相同的树的问题
该函数用来判断二叉树
subRoot
是否是二叉树root
的子树。逻辑解释
空树检查
if(root == NULL) return false;
如果
root
是空树,直接返回false
,因为空树不可能包含任何非空子树。根节点值比较及完整树比较
if(root->val == subRoot->val && isSameTree(root, subRoot)) return true;
如果
root
的当前节点值与subRoot
的根节点值相同,并且root
从当前节点开始的子树与subRoot
完全相同(通过调用isSameTree
函数进行判断),则返回true
。递归检查左右子树
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
如果上述条件都不满足,则递归地检查
root
的左子树和右子树,看其中是否存在与subRoot
相同的子树。如果任意一个子树包含subRoot
,返回true
。总结
这两个函数结合起来可以有效地判断一棵二叉树是否是另一棵二叉树的子树。具体步骤如下:
- 使用
isSubtree
函数遍历root
的每个节点。- 对于每个节点,检查该节点开始的子树是否与
subRoot
完全相同。- 如果找到一个与
subRoot
相同的子树,立即返回true
。- 如果没有找到,继续遍历
root
的左右子树,直到所有节点都检查完毕。这种方法通过递归遍历和子树比较,确保准确判断子树关系。
相关文章:

二叉树经典OJ练习
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 二叉树经典OJ练习 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 前置说…...
【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】008 - make distclean 命令解析
【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】008 - make distclean 命令解析 一、make V=1 distclean 命令解析系列文章汇总:《【OpenHarmony4.1 之 U-Boot 源码深度解析】000 - 文章链接汇总》 本文链接:《【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】008 - mak…...

QTreeView双击任意列展开
一.效果 二.原理 重点是如何通过其他列的QModelIndex(假设为index),获取第一列的QModelIndex(假设为firstColumnIndex)。代码如下所示: QModelIndex firstColumnIndex = model->index(index.row(), 0, index.parent()); 这里要注意index函数的第三个参数,第三个参…...

Linux入门攻坚——26、Web Service基础知识与httpd配置-2
http协议 URL:Uniform Resource Locator,统一资源定位符 URL方案:scheme,如http://,https:// 服务器地址:IP:port 资源路径: 示例:http://www.test.com:80/bbs/…...

相由心生与事出反常必有妖
从端午节之日生病起,已就医三次,快半个月了。医检的结论是老病复发—— 上呼吸道感染 。原本并无大碍,加之“水不在深,有龙则灵”的张龙医生处方得当,现已病情好转。只是“800727”趁人之危,兴灾乐祸地欲从…...
微信小程序---支付
一、判断是否登录 如果没有登录,走前端登录流程,不再赘述 二、获取订单编号 跟自己的后端商议入参,然后获取订单编号 三、通过订单编号获取wx.requestPayment()需要的参数 获取订单编号再次请求后端接口,拿到wx.requestPayme…...

Git学习2 -- VSCode中的Git
看了下,主要的插件有3个。自带的Source Control。第1个是Gitlens,第2个是Git Graph。第三个还有个git history。 首先是Source Control。界面大概是这样的。 还是挺直观的。在第一栏source control,可以进行基本的git操作。主要的git操作都是…...

VC++支持断点续下或续传的功能
VC使用多线程和Socket实现断点续下 一、断点续下的基本原理: 1.断点续传的理解可以分为两部分:一部分是断点,一部分是续传。断点的由来是在下载过程中,将一个下载文件分成了多个部分,同时进行多个部分一起的下载&…...
机器学习数学原理专题——线性分类模型:损失函数推导新视角——交叉熵
目录 二、从回归到线性分类模型:分类 3.分类模型损失函数推导——极大似然估计法 (1)二分类损失函数——极大似然估计 (2)多分类损失函数——极大似然估计 4.模型损失函数推导新视角——交叉熵 (1&#x…...

windows和linux路径斜杆转换脚本,打开即用
前言: windows和linux的目录路径斜杆是相反的,在ssh或者其他什么工具在win和ubuntu传文件时候经常需要用到两边的路径,有这个工具就不用手动去修改斜杆反斜杠了。之前有个在线网站,后来挂了,就想着自己搞一个脚本来用。…...
在Android系统中,查看apk安装路径
在Android系统中,应用通常安装在内部存储的特定目录下。要找到已安装应用的路径,可以通过ADB(Android Debug Bridge)工具来查询。以下是一些步骤和命令,可以帮助你找到应用的安装路径: 使用pm list package…...

管理不到位,活该执行力差?狠抓这4点要素,强化执行力
管理不到位,活该执行力差?狠抓这4点要素,强化执行力 一:强化制度管理 1、权责分明,追责管理 要知道,规章制度其实就是一种“契约”。 在制定制度和规则的时候,民主一点,征求团队成员…...

应届毕业之本科简历制作
因为毕设以及编制岗位面试,最近好久没有更新了,刚好有同学问如何制作简历,我就准备将我自己制作简历的流程分享给各位,到此也算是一个小的结束,拿了工科学位证书毕业去做🐂🐎了。 简历主要包含内…...

SparkOnHive_列转行、行转列生产操作(透视和逆透视)
前言 行专列,列转行是数开不可避免的一步,尤其是在最初接触Hive的时候,看到什么炸裂函数,各种udf,有点发憷,无从下手,时常产生这t怎么搞,我不会啊? 好吧ÿ…...
【人机交互 复习】第2章 Hadoop
一、概念 1.Hadoop 是一个能够对大量数据进行分布式处理的软件框架,并 且是以一种可靠、高效、可伸缩的方式进行处理的, 2.特点: 高可靠性,高效性,高可扩展性,高容错性 运行在Linux平台上,支持…...

国产自研编程语言“仓颉”来了!
在 6.21 召开的华为开发者大会(HDC2024)上,华为自研的国产编程语言“仓颉”终于对外正式发布了! 随着万物互联以及智能时代的到来,软件的形态将发生巨大的变化。一方面,移动应用和移动互联网领域仍然强力驱动人机交互…...

Swarm 集群管理
Swarm 集群管理 简介 Docker Swarm 是 Docker 的集群管理工具。它将 Docker 主机池转变为单个虚拟 Docker 主机。 Docker Swarm 提供了标准的 Docker API,所有任何已经与 Docker 守护程序通信的工具都可以使用 Swarm 轻松地扩展到多个主机。 支持的工具包括但不限…...

从社交网络到元宇宙:Facebook的战略转型
随着科技的迅猛发展和数字化时代的深入,社交网络已不再局限于简单的信息交流和社交互动,而是逐步向更广阔、更深远的虚拟现实空间——元宇宙(Metaverse)转变。作为全球最大的社交网络平台之一,Facebook正在积极推动这一…...

程序猿大战Python——面向对象——继承进阶
方法重写 目标:掌握方法的重写。 当父类的同名方法达不到子类的要求,则可以在子类中对方法进行重写。语法: class 父类名(object):def 方法A(self):代码... class 子类名(父类名):def 方法A(self):代码... 例如,一起来完成&…...

【Linux基础】SSH登录
SSH简介 安全外壳协议(Secure Shell Protocol,简称SSH)是一种加密的网络传输协议,可在不安全的网络中为网络服务提供安全的传输环境。 SSH通过在网络中建立安全隧道来实现SSH客户端与服务器之间的连接。 SSH最常见的用途是远程登…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践
在电商行业蓬勃发展的当下,多平台运营已成为众多商家的必然选择。然而,不同电商平台在商品数据接口方面存在差异,导致商家在跨平台运营时面临诸多挑战,如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...