【数据结构与算法】二叉树题目很难?一句话秒杀基础二叉树题目
💛 前情提要💛
本章节是数据结构
的链式二叉树
的相关知识~
接下来我们即将进入一个全新的空间,对代码有一个全新的视角~
以下的内容一定会让你对数据结构
有一个颠覆性的认识哦!!!
❗以下内容以C语言
的方式实现,对于数据结构
来说最重要的是思想
哦❗
以下内容干货满满,跟上步伐吧~
作者介绍:
🎓 作者: 热爱编程不起眼的小人物🐐
🔎作者的Gitee:代码仓库
📌系列文章&专栏推荐: 《刷题特辑》、 《C语言学习专栏》、《数据结构_初阶》📒我和大家一样都是初次踏入这个美妙的“元”宇宙🌏 希望在输出知识的同时,也能与大家共同进步、无限进步🌟
📌导航小助手📌
- 💡本章重点
- 🍞一.二叉树的概念
- 🥐Ⅰ.二叉树链式结构
- 🍞二.二叉树的遍历
- 🥐Ⅰ.前序遍历
- 🥐Ⅱ.中序遍历
- 🥐Ⅲ.后序遍历
- 🥯Ⅳ.总结
- 🍞三.二叉树OJ题
- 🔥秒杀模板
- 🏷️ 单值二叉树【难度:简单】
- 🏷️ 相同的树【难度:简单】
- 🏷️ 对称二叉树【难度:简单】
- 🥯Ⅷ.总结
- 🫓总结
💡本章重点
-
二叉树链式结构的概念
-
二叉树的三种遍历方式
-
🔥算法思想
🍞一.二叉树的概念
🥐Ⅰ.二叉树链式结构
💡简单来说:
- 就是用
链表
去表示一棵二叉树,即用链表
去表示元素之间的逻辑关系
-
二叉树链式结构不同于
堆
【因为堆
又称为二叉树的顺序结构】-
二叉树的链式结构可以存储任意
树
(包括:普通二叉树,满二叉树,完全二叉树等) -
而二叉树的顺序结构存储更多存储的是
完全二叉树
、满二叉树
,而不存储普通二叉树
,否则会造成空间浪费
-
👉二叉树可分两种:
-
空树
-
非空树:根节点、根节点的左子树、根节点的右子树组成(如下图:)
👉代码实现:
typedef int BTDataType;typedef struct BinaryTreeNode{struct BinaryTreeNode* left; struct BinaryTreeNode* right;BTDataType data;}BTNode;
❗综上:
-
不难发现二叉树的定义正是
递归式
-
所以我们正可以通过
递归
的方式去遍历整个二叉树
✊所以接下来我们就开始实现吧~
🍞二.二叉树的遍历
🥐Ⅰ.前序遍历
💡前序遍历: 又称为先根遍历
-
即访问根结点的操作发生在遍历其左右子树之前
-
简单来说:优先访问
根节点
,继而访问根节点的左子树
,最后再访问根节点的右子树
❗特别注意:
-
上述所说的
根节点
不仅仅指的是整棵树的根节点
,也指每一个结点【因为每一个结点都可以当作一个根节点
来看待】 -
因此每一个结点都可以以
根节点
看待【即一棵完整的树,被拆分成多个子树看待】
✊动图示例:
👉代码实现:
void PrevOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}//访问根结点printf("%d ", root->data);//访问左子树PrevOrder(root->left);//访问右子树PrevOrder(root->right);}
👆递归展示:
✨综上: 每个结点都可以看作一棵树【即拆分成子问题看待】
-
每次先访问
根结点
-
继而访问
左子树
,直至访问完全整棵树中的左子树
-
最后访问
右子树
,直至访问完全整棵树中的右子树
🥐Ⅱ.中序遍历
💡前序遍历: 又称为中根遍历
-
即访问根结点的操作发生在遍历其左右子树之中(间)
-
简单来说:先递归遍历完
根节点的左子树
,而后递归返回时访问根节点
,最后再递归访问根节点的右子树
❗特别注意:
-
上述所说的
根节点
不仅仅指的是整棵树的根节点
,也指每一个结点【因为每一个结点都可以当作一个根节点
来看待】 -
因此每一个结点都可以以
根节点
看待【即一棵完整的树,被拆分成多个子树看待】
✊动图示例:
👉代码实现:
void InOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}//访问左子树InOrder(root->left);//访问根结点printf("%d ", root->data);//访问右子树InOrder(root->right);}
✨综上: 每个结点都可以看作一棵树【即拆分成子问题看待】
-
每次先访问
左子树
,直至访问完全整棵树中的左子树
-
继而访问
根节点
-
最后访问
右子树
,直至访问完全整棵树中的右子树
🥐Ⅲ.后序遍历
💡前序遍历: 又称为后根遍历
-
即访问根结点的操作发生在遍历其左右子树之后
-
简单来说:优先访问
根节点的右子树
,继而访问根节点
,最后再访问根节点的左子树
❗特别注意:
-
上述所说的
根节点
不仅仅指的是整棵树的根节点
,也指每一个结点【因为每一个结点都可以当作一个根节点
来看待】 -
因此每一个结点都可以以
根节点
看待【即一颗完整的树,被拆分成多个子树看待】
✊动图示例:
👉代码实现:
void PostOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}//访问左子树PostOrder(root->left);//访问右子树PostOrder(root->right);//访问根结点printf("%d ", root->data);}
✨综上: 每个结点都可以看作一棵树【即拆分成子问题看待】
-
每次先访问
左子树
,直至访问完全整棵树中的左子树
-
继而访问
右子树
,直至访问完全整棵树中的右子树
-
最后再访问
根结点
🥯Ⅳ.总结
✨综上:三种二叉树的遍历方式,本质就是调换访问左子树
、右子树
、根节点
的语句次序,然后程序便会自动递归
帮我们访问完整棵树的所有结点啦~
➡️相信大家对三种遍历方式
有不一样的看法了吧🧡
🍞三.二叉树OJ题
🔥秒杀模板
❗ 秒杀口诀:
-
左右子树之间的
逻辑关系
➕树的遍历方式
-
1️⃣左右子树之间的
关系
:指的是为了达到题目要求的结果,我们需要让左、右子树之间达成什么样的关系【Eg:逻辑关系(&&、||、……)、算数关系(+、-、……)、……】 -
2️⃣找出
逻辑关系
后,只需要结合合适的遍历方式
,相当于找到通式
,便可以通过通式
解决题目了
❓具体是怎么运用呢?
✊让我们用题目来实际运用分析吧~
🏷️ 单值二叉树【难度:简单】
🔍题目传送门:
Leetcode:965. 单值二叉树 |
---|
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树
只有给定的树是单值二叉树时,才返回 true
,否则返回 false
- 示例 1:
输入:[1,1,1,1,1,null,1]输出:true
- 示例 2:
输入:[2,2,2,5,2]输出:false
💡解题关键:
-
我们只需要遍历二叉树的每一个结点,一一比较每个结点的值是否相同
-
本题就可以运用我们的秒杀技巧
👉秒杀分析:
-
此处先找到左、右子树之间的
逻辑关系
- 我们将视角放到整体的树上,只看这个树的左、右子树之间通过怎样的
逻辑关系
才能实现题目要求(如下:)
- 我们将视角放到整体的树上,只看这个树的左、右子树之间通过怎样的
➡️如上我们便可发现: 题目需要我们去判断每一个结点的值是否相同,那此时对于上面的树来说,我们就需要判断左子树
、右子树
里的每一个结点是否与根节点
的值相同
-
1️⃣那此时我们便找到合适的
遍历方式
:前序遍历
-
因为每次遍历下来直接先判断根节点的值是否相同,不相同就可以直接返回
false
,不再需要递归下去 -
否则,若用其它遍历方式,就需要在判断完子树的所有结点后,返回的时候才判断
根节点
-
➡️又因为: 需要左子树
与右子树
递归判断完后返回的结果都为true
后,整棵树才真正的满足单值二叉树
- 2️⃣那此时我们便知道左、右子树之间的
逻辑关系
为&&
【只有左右俩操作数都满足时,才真正的满足】
👆综上:
-
秒杀口诀为:
&&
➕前序遍历
-
本质:将每个结点与自己的孩子结点进行比较,看是否相同,一直比较直至递归完整棵树【利用的是:
等号具有传递性
】
❗特别注意:
-
当根节点或者二叉树为
NULL
的时候,就返回true
,因为没有值的结点可以不参与判断,有值的才去进行判断 -
在进行每一个结点与孩子结点比较的时候,需要判断提前孩子结点是否为
NULL
,因为只有不为NULL
才能访问到这个结点的val
;否则会造成非法访问内存
✊动图示例:
👉代码实现:
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);}
➡️补充:
-
这里设计得也很巧妙,即左子树已经是单值的情况下,才走右子树
-
否则,若左子树有不相等的情况下,就可以直接不走右子树了
🏷️ 相同的树【难度:简单】
🔍题目传送门:
Leetcode:100. 相同的树 |
---|
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的
示例 1:
输入:p = [1,2,3], q = [1,2,3]输出:true
示例 2:
输入:p = [1,2], q = [1,null,2]输出:false
示例三:
输入:p = [1,2,1], q = [1,1,2]输出:false
💡解题关键:
-
两棵树同时遍历,一一比较是否相同
-
但这里我们不写相等的递归结束条件,而是写不相等的条件,因为这里即需要判断
树的结构
也要判断相同结构下相同结点的值
相等,所以这里相等的条件不好描述出来 -
但如果是写当树不相等的条件的话,一旦判断不相等,那一定是不相同的二叉树
👉秒杀分析:
- 这里的分析和上题的如出一辙,所以我们选择
&&
➕前序遍历
➡️做题思路:
-
1️⃣当两棵树都为空树(
NULL
)or 都比较完前面的结点直至NULL
的时候,证明前面判断的每个结点都是相同的,所以返回true
-
2️⃣通过判断各自树的当前结点是否
NULL
,从而判断树的结构是否相同,也预防了对NULL
结点的访问 -
3️⃣判断完结构后,再进行最后的值判断
✊动图示例:
❗特别注意:
-
上述的动图中看上去是两棵树分开走的,但再代码实现中其实是一起走的
-
且返回的时候其实是两棵树共同返回的是一个
true
,上述动图只是为了好表达才这样表示
👉代码实现:
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//1.树都为NULL的时候 -- 相等//2.比较比到 NULL 的时候 == 前面都比完了,那就相等if (p == NULL && q == NULL){return true;}//判断p树和q树结构是否相同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);}
🏷️ 对称二叉树【难度:简单】
🔍题目传送门:
Leetcode:101. 对称二叉树 |
---|
给你一个二叉树的根节点 root
, 检查它是否轴对称
- 示例 1:
输入:root = [1,2,2,3,4,4,3]输出:true
- 示例 2:
输入:root = [1,2,2,null,3,null,3]输出:false
💡解题关键:
-
本题类似于上题,可复用上题的思路
-
这里的思路是拆分子问题,将一棵树的左、右子树看成两棵树,去复用上题的代码
👉秒杀分析:
- 这里的分析和上题的如出一辙,所以我们选择
&&
➕前序遍历
❗特别注意:
-
当树为空树(
NULL
),就直接返回true
,因为空树没有结点,本来就是对称的 -
因为这里判断的是
对称
,所以:-
左子树中的左孩子是与右子树中的右孩子比较的
-
左子树中的右孩子是与右子树中的左子树比较的
-
👉代码实现:
bool _isSymmetric(struct TreeNode* left, struct TreeNode* right){if (left == NULL && right == NULL){return true;}if (left == NULL || right == NULL){return false;}if (left->val != right->val){return false;}return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);}bool isSymmetric(struct TreeNode* root) {if (root == NULL){return true;}return _isSymmetric(root->left, root->right);}
🥯Ⅷ.总结
✨综上:就是秒杀模板
的相关内容啦~
➡️相信大家对这些题目了如指掌了吧,也十分建议同学们多多练习中间的思想哟🧡
🫓总结
综上,我们基本了解了数据结构中的 “二叉树链式结构” 🍭 的知识啦~~
恭喜你的内功又双叒叕得到了提高!!!
感谢你们的阅读😆
后续还会继续更新💓,欢迎持续关注📌哟~
💫如果有错误❌,欢迎指正呀💫
✨如果觉得收获满满,可以点点赞👍支持一下哟~✨
开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系