婚纱销售网站,wordpress留言插件,php做网站需要html,莱芜论坛最新消息文章目录 前言一. N叉树的层序遍历1.1 题目链接#xff1a;https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/1.2 题目分析#xff1a;1.3 思路讲解#xff1a;1.4 代码实现#xff1a; 二. 二叉树的锯齿形层序遍历2.1 题目链接#xff1a;htt… 文章目录 前言一. N叉树的层序遍历1.1 题目链接https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/1.2 题目分析1.3 思路讲解1.4 代码实现 二. 二叉树的锯齿形层序遍历2.1 题目链接https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/2.2 题目分析2.3 思路讲解2.4 代码实现 三. 二叉树最大宽度3.1 题目链接https://leetcode.cn/problems/maximum-width-of-binary-tree/description/3.2 题目分析:3.3 思路讲解3.4 代码实现 四. 在每个树行中找最大值4.1 题目链接https://leetcode.cn/problems/find-largest-value-in-each-tree-row/descri4.2 题目分析4.3 思路讲解4.4 代码实现 小结 前言 上篇我们介绍了BFS算法的思想和代码实现本篇我们将结合具体题目进一步深化对于BFS算法的理解运用。 一. N叉树的层序遍历
1.1 题目链接https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
1.2 题目分析
给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。与二叉树不同该树可能有多个孩子节点在层序遍历令下一层节点入队列时需要注意遍历方式
1.3 思路讲解
层序遍历即可~仅需多加⼀个变量⽤来记录每⼀层结点的个数就好了。
1.4 代码实现
class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ret;//返回数组queueNode* q;//遍历队列if(rootnullptr){return ret;}//处理特殊情况q.push(root);while(q.size()){int szq.size();//该层节点个数vectorint temp;//存储该层节点的值for(int i0;isz;i){auto tq.front();q.pop();temp.push_back(t-val);//下一层节点入队列for(auto child:t-children){q.push(child);}}ret.push_back(temp);//更新}return ret;}
};二. 二叉树的锯齿形层序遍历
2.1 题目链接https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
2.2 题目分析
要求进行二叉树的层序遍历遍历时按照奇数层从左到右偶数层从右到左的方式进行遍历
2.3 思路讲解 本题的核心还是在于二叉树的层序遍历我们可以通过level来记录层数判断遍历方向。 2.4 代码实现
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorint ret;//返回数组queueTreeNode* q;//队列if(rootnullptr){return ret;}//处理特殊情况q.push(root);int level1;//记录层数while(q.size()){int szq.size();//该层节点个数vectorint temp;//存储该层节点的值for(int i0;isz;i){auto tq.front();q.pop();temp.push_back(t-val);//下一层节点入队列if(t-left) q.push(t-left);if(t-right) q.push(t-right);}if(level%20){reverse(temp.begin(),temp.end());}//处理偶数层情况ret.push_back(temp);level;//更新层数}return ret;}
};三. 二叉树最大宽度
3.1 题目链接https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
3.2 题目分析:
给定二叉树求其最大宽度其中宽度是指一层里面起始节点到最终节点的节点数空节点也算一个节点
3.3 思路讲解
思路一层序遍历计算节点个数会超出内存限制 利用层序遍历的思想一层层计录节点个数将空节点也包含在内但在遇到极端单链情况时节点数目会异常庞大导致超出内存限制 思路二利用二叉树的顺序存储计算左右下标 依旧是利⽤层序遍历但是这⼀次队列⾥⾯不单单存结点信息并且还存储当前结点如果在数组中存储所对应的下标在我们学习数据结构 - 堆的时候计算左右孩⼦的⽅式。 这样我们计算每⼀层宽度的时候⽆需考虑空节点只需将当层结点的左右结点的下标相减再加1即可。 但是这⾥有个细节问题如果⼆叉树的层数⾮常恐怖的话我们任何⼀种数据类型都不能存下下标的值。但是没有问题因为 • 我们数据的存储是⼀个环形的结构 • 并且题⽬说明数据的范围在 int 这个类型的最⼤值的范围之内因此不会超出⼀圈 • 因此如果是求差值的话我们⽆需考虑溢出的情况。 此处下标的记录需要用unsigned int
3.4 代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vectorpairTreeNode*,unsigned int q;//用数组模拟队列if(rootnullptr){return 0;}//处理特殊情况q.push_back({root,1});unsigned int width1;//宽度while(q.size()){//先更新本层宽度auto [x1,y1]q[0];auto [x2,y2]q.back();widthmax(width,y2-y11);vectorpairTreeNode*,unsigned int temp;//存储数组for(auto [x,y]:q){//左右节点入队列if(x-left){temp.push_back({x-left,2*y});}if(x-right){temp.push_back({x-right,2*y1});}}qtemp;//更新队列}return width;}
};四. 在每个树行中找最大值
4.1 题目链接https://leetcode.cn/problems/find-largest-value-in-each-tree-row/descri
4.2 题目分析
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
4.3 思路讲解 本题核心仍然为层序遍历只需记录每一层的最大值即可 4.4 代码实现
class Solution {
public:vectorint largestValues(TreeNode* root) {vectorint ret;//返回数组queueTreeNode* q;if(rootnullptr){return ret;}//处理特殊情况q.push(root);while(q.size()){int szq.size();//本层节点数int tempINT_MIN;//记录本层最大值for(int i0;isz;i){auto tq.front();q.pop();tempmax(temp,t-val);//下一层入队列if(t-left){q.push(t-left);}if(t-right){q.push(t-right);}}ret.push_back(temp);}return ret;}
};小结 在BFS的世界里我们能够感受到一种近乎哲学的智慧它并不急功近利而是循序渐进逐步展开。每一层的遍历每一个节点的访问都是对“问题解答”的一步步接近。而当问题的答案最终浮现我们也能够感叹原来最简单的思路往往是最伟大的。 本篇关于BFS算法的介绍就暂告段落啦希望能对大家的学习产生帮助欢迎各位佬前来支持斧正
