【LeetCode】102.二叉树的层序遍历
题目描述
思路分析
- 对于本题我给出两种解法，也是比较经典的两种思路，一个是DFS【深度优先搜索】以及BFS【广度优先搜索】。
- 对于DFS，需要通过记录遍历的深度，为每一层开辟或新加结点，以达到分割输出每一层结点的效果；
- 对于BFS，需要通过队列来进行辅助，只需在原有的BFS代码模板基础上，加一个size去获取每一层的结点个数即可，到那一层的时候出队对应个数的也可以达到分割输出每一层结点的效果
代码详解
- 给出两种解法，分别是DFS和BFS
DSF——深度优先搜索
class Solution { private: void DFS(TreeNode* cur, vector<vector<int>>& ret, int dep) { if(cur == NULL) return; if(ret.size() <= dep) //过结果集大小 《= 当前层深度，表明第一层访问本层结点 { vector<int> vec; vec.push_back(cur->val); //创建一个小结果集将其放入 ret.push_back(vec); } else { //若是结果集大小 > 当前层深度，表明已经访问过，直接加入大结果集的当前层小结果集中即可 ret[dep].push_back(cur->val); } //递归其左右子树，开始下一层的访问 DFS(cur->left, ret, dep + 1); DFS(cur->right, ret, dep + 1); //dep + 1表示深度 + 1 } public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; int dep = 0; DFS(root,result,dep); return result; } };
- 稍微讲解一下DFS的代码，可能有点难以理解，首先看到是需要三个参数，一个是当前所访问的结点，一个是大的结果集，一个是递归深度，这个在我下面所画的算法图中都有展现出来，接下去说一下存放结果集的过程，主要就是通过大结果集的size()大小和当前递归深度做一个比较，若是<=则表示是第一个次遍历到这一层，表明还没有为这一层开辟一个存放数据的小结果集，就开辟出来然后存入数据，若是【ret.size() > dep】了，那就表明此次访问的还是这一层，只需要将新结点追加在这一层之后即可
- 放入当前结点后便递归其左右子树，当然dep深度也要++，通过这样的逻辑，就可以将一棵树中的所有结点放入一个二维的结果集中
- 以下是我画的算法图解，仅供参考，你可自己去模拟着画画，强调一点，对于递归要多画展开图
BSF——广度优先搜索
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> qu; //二叉树类型队列 vector<vector<int>> result; //存放遍历结点结果集 if(root != NULL) qu.push(root); //存入根结点 //开始队列操作 while(!qu.empty()) //直至队列为空 { int sz = qu.size(); //获取当前队列的大小 vector<int> vec; //装载每一层的树层结点 for(int i = 0;i < sz; ++i) { TreeNode* node = qu.front(); //获取当前队列的队头元素 qu.pop(); //出队队头元素 vec.push_back(node->val); //子树的入队 if(node->left) qu.push(node->left); //左孩子入队 if(node->right) qu.push(node->right); //右孩子入队 } result.push_back(vec); //每一层结点放入结果集 } return result; } };
- 然后来说说BFS的具体求解过程
- 上述就是BFS层序遍历的过程，你可试着自己模拟看看
【LeetCode】965.单值二叉树
题目描述
思路分析
- 本题的描述很简单，【单值二叉树】就是树中的每一个值都是相等的
- 通过图示可以看出，要去比较所有树中的结点值是否一致，首先我们比较的是根节点和其左右孩子结点，若是相同呢，做去递归其左右子树继续进行判断，也就是每次都进行==根节点与去左右孩子结点的值是否一致==，通过这三者的比较，若是在比较的过程中发现有不相等的情况，则立即
return false; - 然后通过不断递归，直到当前根节点为
NULL为止，表示从根节点到这个结点的所有结点值均相同。但是呢并不是左子树相同就行，还要去递归其右子树，只有左右子树均相同后，才表示所有的结点值相同，那么这就是一棵【单值二叉树】
代码详解.
- 下面是代码详解
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); }
- 最后的这个
isUnivalTree(root->left) && isUnivalTree(root->right)使用到的是一个【逻辑与】的操作符，它的运算规则是操作符两边的表示式均为真那么整个结果才为真，若是有一个为假则整个表达式为假 —— 如果不理解可以看看我的操作符汇总大全 - 那这个意思转换过来就是==当前根节点与其左右子树的值均相等==
【LeetCode】100.相同的树【⭐】
本题对于后面的两题都很有帮助，因此要重点理解
题目描述
思路分析
- 来看看本题的思路，刚才我们在比较一棵树中的结点是否相同，那只需要左右子树进行一个递归即可，但是现在有两棵树了，那该怎么办呢？可以看到，主函数接口中也是给到了两个指向根节点的指针，那其实套路也是一样的，只是需要考虑的情况多了一些
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
- 首先就要考虑的是两棵树是不是都是空树的情况，若都是空树，则表示它们也是相等的
- 其次的话就是要考虑当前传入的两棵树的结点一个空，一个非空的情况，这个条件不可以写在第一个，因为这种情况是包含在两个都非空的情况下的，若是将这个条件写在第一行，那么两棵树进来的当前结点一个空、一个非空就会被【return false】，那就不对了
- 在空和非空判断完了之后就是结点值的判断，这个很直观，不相同返回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); }
【LeetCode】101.对称二叉树
题目描述
思路分析
- 好，我们来分析一下思路，对于本题的对称二叉树，也叫做【镜像二叉树】，就是你在家里照镜子一下，你动动左手，那镜子中的人动的就是右手；你动动右手，那镜子中的人动的就是左手。那二叉树也是一下，我的左子树对应过来就是你的右子树，你的右子树呢对应过来就是我的左子树。==上面这一段论述你不要以为没有用，可以帮助你理解代码==
代码详解
//不到万不得已不要去破坏原有的结构 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->right) && isSameTree(p->right,q->left); } bool isSymmetric(struct TreeNode* root){ if(root == NULL) return true; return isSameTree(root->left,root->right); }
- 可以看到，我复用了上面那题【相同的树】代码，但是仔细看呢，却发现我修改了一些 ，也及时两棵树的左右子树在递归的时候要往不同的子树走，==我走左，你走右；我走右，你就走左==
- 下面是图示
【LeetCode】226.翻转二叉树
因为刚才讲到了镜像二叉树，和本次的翻转二叉树很像，因此将本题也纳入讲解
题目描述
思路分析
- 本题我依旧是给出两个思路，一个是DFS，一个是BFS。
- DFS很简单，很好理解，因为是翻转二叉树，只需要翻转其左右孩子即可，然后接下向下递归，进行翻转；
swap(root->left,root->right); invertTree(root->left); invertTree(root->right);
- BFS的话和我们上面层序遍历的代码基本一致，只需要在获取到当前结点后交换其左右孩子然后入队即可，后面出队就是翻转后的二叉树
swap(node->left,node->right);
代码详解
DFS
class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root == NULL) return root; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } };
- 以下是DFS的翻转过程
BFS
- BFS不做过多讲解吗，核心就在于取到当前队头结点后不要直接将其左右孩子入队，将他们交换一下再入队即可
class Solution { public: TreeNode* invertTree(TreeNode* root) { queue<TreeNode*> qu; if(root == NULL) return NULL; qu.push(root); while(!qu.empty()) { int sz = qu.size(); for(int i = 0;i < sz; ++i) { TreeNode* node = qu.front(); qu.pop(); //此时node已经取到队头结点 swap(node->left,node->right); //继续遍历左右孩子 if(node->left) qu.push(node->left); if(node->right) qu.push(node->right); } } return root; } };
【LeetCode】572.另一棵树的子树
上一题是一段小插曲，本题也需要使用到No.100的代码，也就是【相同的树】，不过本题稍微难理解一些，所以我会讲得详细一点
题目描述
- 首先来看一下有关题目的描述
思路分析
- 本题的意思就是在一棵树中找另一棵树的子树，那有同学说，这该如何去比较呢？
- 在上面我们学会了如何去比较一棵树中有无相同的结点、两棵树是否相同以及如何去反转一棵树，但是现在的需求是要在一棵树中找到是否包含了另一棵树，存在一个嵌套的逻辑，是会感觉有点烧脑起来了:ocean:
- 于是有的同学就找了各种办法，去左右子树里面递归寻找，一个个翻转控制对比，然后把自己绕晕了，其实这道题只要思路对了，是很好解决的，虽然我们是要找是否存在另一颗子树，但是呢这个过程还是在比较两棵树是否是相同的，因此还是需要用到我们上面写到过的【比较两棵树是否相同】的代码逻辑，就是在主接口中在做一些初始判断即可
- 流程如下
- 判断主树是否为空，若为空则不可能包含子树，因为题目条件给出子树不为空
- 判断两棵树的根是否一致，若是一致表示这是两棵相同的树
- 分别递归其左右子树进行查找对比，复用isSameTree()的代码逻辑
代码详解
//全比一下 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){ //提示中给出子树不可能为空，因此root为空就表示不存在子树 if(root == NULL) return false; //首先比较两棵树的根是否相同 if(isSameTree(root,subRoot)) return true; //根不同则去递归root的左右子树继续比较 return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); //使用逻辑或，左子树找到了就无需在往右子树寻找 }
- 这里要说明的一点就是在递归的时候为什么用的是【| |】，而不是【&&】，这就需要你自己思考了，这个符号叫做==按位或==，设想你在左子树中已经找到了包含的子树，那还需要到右子树中去寻找吗？当然是不需要了，按位或的逻辑就是有一个真那整个表达式即为真
递归算法图分解
本题还有一些坑，而且代码可能晦涩难懂一些，因为我画一下递归展开图给你看看，你也可以尝试自己画画
- 首先是对于正常的情况。通过
isSameTree()去比较了两个根节点与其左右孩子结点是否相同，很明显③和④已经不相同的，所以root便向其左子树递归，此时再去比较就可以发现在root主树中找到了这棵子树，所以【return true】
- 然后是需要注意的情况，可以看到在两棵树中只要哪棵树哪里多出来一个结点，那这两棵树就是不同的，对于DFS来说它会一直递归，直至遍历完所有的树为止
- 因为当前根是不同的不代表子树里没有相同的，所以都要进行一个比较
【NowCoder】KY11.二叉树遍历
本题是从【牛客】摘录过来的，也是比较经典的一道题目 对于牛客来说，和力扣不一样的地方在于它是==IO型OJ==，而力扣则是==接口型OJ==，对于IO型的OJ呢我们需要和在VS里面一样，头文件、main函数均需要自己添加，也就是输入输出都由自己来完成；但是对于接口型OJ你只需实现题目给出的这一部分功能即可，但是相对许多公司的面试来说，大多都会采用【牛客】这个平台来进行面试，所以大家在熟悉了力扣之后，对于牛客也要多熟悉熟悉
题目描述
思路分析
- 本题的意思是这样的，你需要输入一些先序遍历后的二叉树序列，字母表示结点值，#表示空树，然后你要根据这个先序序列去构造一棵二叉树，然后再输出其中序遍历后的结果
先序序列转二叉树视频教学
- 但是要怎么去将给出的这一个先序序列构造成一棵二叉树呢，因为这不好用文字讲解，因此我将给出视频做讲解:tv:
[video(video-tDMBwVAP-1671257824075)(type-csdn)(url-live.csdn.net/v/embed/263…)] ——【微信手机端看不到】
看了视频讲解之后，相信你对先序遍历如何去进行构造应该有了一定的了解，接下去我们将这个思路转化为代码的形式
- 首先第一步，我们要将这个重构的过程封装成一个函数，因为我们肯定要去进行递归，先给出需要传入的参数，说明一下这里为什么要一个指针来接受，而且在主函数中我传入了一个变量的地址，这个变量是用来遍历这个二叉树的先序序列的，这和我们上面在说C语言版本的先序遍历是一个道理，若是在递归的过程中使用的仅仅是普通的变量，虽然递归进去这个i是发生了变化，但是呢在递归回调的时候，却又回到了首次递归进去的那个值，因此在递归右子树时就会出问题，所以这里我们要使用【指针来接受这个变量的地址】，==这样每次递归进去内部的修改就可以带动外部的这个值的修改了==
BTNode* reBuildTree(char* str, int *pi)
- 一开始首先就是要判断一下传进来的字符是否为【#】，若是则表示其为一棵空树，我们单独做处理，返回NULL即可，但是不要忘了将这个遍历先序序列数组的指针后移，便于下一次的访问
- 接下去就是正常的情况，因为我们需要构建出一棵树，树的每一个结点值是需要一棵空间才存放的，而不仅仅是一个char值罢了，因此我们在上面也需要封装一个树结点的结构体，在遇到字母的时候就开辟出一块空间去存放这个结点值，然后继续去递归其左右子树即可，直到碰到【#】就会return递归右子树了
//若有值，则创建结点存放 BTNode* node = (BTNode *)malloc(sizeof(BTNode)); node->data = str[(*pi)++]; //赋值后指向字符序列下一个字符 //递归当前结点的左右子树 node->lchild = reBuildTree(str,pi); node->rchild = reBuildTree(str,pi);
- 然后有关中序序列的遍历很简单，就是普通的递归，便不做说明
代码详解
- 下面是整体的代码展示
#include <stdio.h> #include <stdlib.h> typedef struct BinaryTreeNode{ char data; struct BinaryTreeNode* lchild; struct BinaryTreeNode* rchild; }BTNode; //指针接收地址 BTNode* reBuildTree(char* str, int *pi) { if(str[*pi] == '#') { //#表示空树 (*pi)++; return NULL; } //若有值，则创建结点存放 BTNode* node = (BTNode *)malloc(sizeof(BTNode)); node->data = str[(*pi)++]; //赋值后指向字符序列下一个字符 //递归当前结点的左右子树 node->lchild = reBuildTree(str,pi); node->rchild = reBuildTree(str,pi); return node; } void InOrder(BTNode* root) { if(root == NULL) return; InOrder(root->lchild); printf("%c ",root->data); InOrder(root->rchild); } int main() { int i = 0; char str[100]; scanf("%s",str); BTNode* reTree = reBuildTree(str,&i); InOrder(reTree); return 0; }
持续更新中，不断汇总二叉树面试题📰📰📰📰📰
DFS与BFS万能模板【❗❗❗】
- 可以看到，在二叉树面试题的求解过程中，我大量使用到了两种搜索算法【DFS】和【BFS】，这也是两个非常常用的算法，因此我将给出它们的万能模板，之后遇到题目只需要根据题意进行一些改动即可
==DFS==
class Solution { public: void order(TreeNode* cur, vector<vector<int>>& result, int depth) { if (cur == nullptr) return; if (result.size() == depth) result.push_back(vector<int>()); result[depth].push_back(cur->val); order(cur->left, result, depth + 1); order(cur->right, result, depth + 1); } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; int depth = 0; order(root, result, depth); return result; } };
==BFS==
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(root); vector<vector<int>> result; while (!que.empty()) { int size = que.size(); vector<int> vec; // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的 for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } result.push_back(vec); } return result; } };
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)