seo建站教学,手机软件商店下载,联合智慧旅游建设旅游门户网站,南京网站开发南京乐识权威算法沉淀——队列宽度优先搜索#xff08;BFS#xff09; 01.N 叉树的层序遍历02.二叉树的锯齿形层序遍历03.二叉树最大宽度04.在每个树行中找最大值 队列 宽度优先搜索算法#xff08;Queue BFS#xff09;是一种常用于图的遍历的算法#xff0c;特别适用于求解最短路径… 算法沉淀——队列宽度优先搜索BFS 01.N 叉树的层序遍历02.二叉树的锯齿形层序遍历03.二叉树最大宽度04.在每个树行中找最大值 队列 宽度优先搜索算法Queue BFS是一种常用于图的遍历的算法特别适用于求解最短路径或最少步数等问题。该算法通常用于在图中寻找从起点到目标点的最短路径。
基本思想
初始化队列 将起始节点放入队列中。BFS遍历 从队列中取出一个节点遍历与该节点相邻且未访问过的节点将其加入队列。标记已访问 标记已访问的节点避免重复访问。重复步骤2和3 直到队列为空。
这个算法适用于无权图的最短路径问题。在搜索的过程中每一层级的节点都会被依次访问直到找到目标节点。
具体步骤
将起始节点加入队列。进行循环直到队列为空 a. 从队列中取出一个节点。 b. 如果该节点是目标节点返回结果。 c. 否则将与该节点相邻且未访问过的节点加入队列并标记为已访问。
这种算法适用于许多场景例如迷宫问题、游戏中的寻路问题、网络路由算法、树问题等。在这些问题中它能够有效地找到最短路径或最优解。
01.N 叉树的层序遍历
题目链接https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。
示例 1
输入root [1,null,3,2,4,null,5,6]
输出[[1],[3,2,4],[5,6]]示例 2 输入root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] 提示
树的高度不会超过 1000树的节点总数在 [0, 10^4] 之间
思路
在树的层序遍历中经常要使用到的就是队列和宽度优先搜索算法这是一道经典的队列和宽度优先搜索算法模板题 初始化一个空的二维向量 ret 用于存储层次遍历的结果。 如果根节点 root 为空直接返回空向量 ret。 创建一个队列 q 并将根节点入队。 进入主循环该循环将处理每一层的节点 a. 获取当前队列的大小即当前层的节点数。 b. 创建一个临时向量 tmp 用于存储当前层的节点值。 c. 对于当前层的每个节点 出队一个节点 t。将节点值 t-val 存入 tmp。将该节点的所有子节点入队如果子节点非空。 d. 将 tmp 存入 ret。 返回最终的层次遍历结果 ret。
代码
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};
*/class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ret;queueNode* q;if(!root) return ret;q.push(root);while(q.size()){int nq.size();vectorint tmp;for(int i0;in;i){Node* tq.front();tmp.push_back(t-val);for(Node* x:t-children) if(x) q.push(x);q.pop();}ret.push_back(tmp);}return ret;}
};02.二叉树的锯齿形层序遍历
题目链接https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[20,9],[15,7]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[] 提示
树中节点数目在范围 [0, 2000] 内-100 Node.val 100
思路
这一题我们仔细理解题意我们不难发现这题和上一题的区别就是在偶数行时需要逆序所以我们只要再添加一个偶数列逆序的操作即可其余同上。
引入一个标志变量 flag用于标识当前层次是奇数层还是偶数层。初始化为0。初始化一个队列 q 用于层次遍历以及一个二维向量 ret 用于存储结果。如果根节点 root 为空直接返回空向量 ret。将根节点入队。进入主循环该循环处理每一层的节点 a. 获取当前队列的大小即当前层的节点数用 s 表示。 b. 递增 flag。 c. 创建一个临时向量 tmp 用于存储当前层的节点值。 d. 对于当前层的每个节点 出队一个节点 t。将节点值 t-val 存入 tmp。如果节点 t 的左子节点非空将其入队。如果节点 t 的右子节点非空将其入队。 e. 如果 flag 为偶数反转 tmp 中的元素顺序。 f. 将 tmp 存入 ret。 返回最终的层次遍历结果 ret。
代码
/*** 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:vectorvectorint zigzagLevelOrder(TreeNode* root) {queueTreeNode* q;vectorvectorint ret;if(!root) return ret;q.push(root);int flag0;while(q.size()){int sq.size();flag;vectorint tmp;for(int i0;is;i){TreeNode* tq.front();tmp.push_back(t-val);q.pop();if(t-left) q.push(t-left);if(t-right) q.push(t-right);}if(flag%20) reverse(tmp.begin(),tmp.end());ret.push_back(tmp);}return ret;}
};03.二叉树最大宽度
题目链接https://leetcode.cn/problems/maximum-width-of-binary-tree
给你一棵二叉树的根节点 root 返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1
输入root [1,3,2,5,3,null,9]
输出4
解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。示例 2
输入root [1,3,2,5,null,null,9,6,null,7]
输出7
解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。示例 3
输入root [1,3,2,5]
输出2
解释最大宽度出现在树的第 2 层宽度为 2 (3,2) 。提示
树中节点的数目范围是 [1, 3000]-100 Node.val 100
思路
这道题最大的坑点在于如果二叉树极度不平衡若使用模拟的方式空节点也进行插入操作去计算的话空间是远远不够的所以这里我们不能像前面两题这样操作我们可以通过计算每层插入节点的头和尾下标差值并使用vector来模拟队列操作每次都覆盖前一层以防超出内存还有计算差值我们使用无符号整型这样我们可以避免数据溢出带来的计算错误的值
定义一个队列 q其中每个元素是一个 pair包含一个二叉树节点指针和该节点在完全二叉树中的编号。将根节点和其对应编号 1 放入队列 q 中。初始化一个变量 ret 用于存储最大宽度。进入主循环该循环用于遍历二叉树的每一层。 a. 获取当前队列的首尾元素即队列中最左边和最右边的节点及其编号。 b. 计算当前层的宽度即 y2 - y1 1其中 y1 是最左边节点的编号y2 是最右边节点的编号。 c. 更新 ret取 ret 和当前层宽度的较大值。 d. 创建一个临时队列 tmp。 e. 遍历队列 q 中的每个节点 如果节点有左子节点将左子节点及其编号编号乘以 2加入 tmp。如果节点有右子节点将右子节点及其编号编号乘以 2 加 1加入 tmp。 f. 将 tmp 赋值给队列 q。 返回最终的宽度 ret。
代码
/*** 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;q.push_back({root,1});unsigned int ret0;while(q.size()){auto [x1,y1]q[0];auto [x2,y2]q.back();retmax(ret,y2-y11);vectorpairTreeNode*,unsigned int tmp;for(auto [x,y]:q){if(x-left) tmp.push_back({x-left,y*2});if(x-right) tmp.push_back({x-right,y*21});}qtmp; }return ret;}
};04.在每个树行中找最大值
题目链接https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
示例1
输入: root [1,3,2,5,3,null,9]
输出: [1,3,9]示例2
输入: root [1,2,3]
输出: [1,3]提示
二叉树的节点个数的范围是 [0,104]-231 Node.val 231 - 1
思路
根据前面几个题型我们不难想到无非就是在层序遍历的基础上增加一个每层的最大值计算在之前的基础上增加条件即可。
定义一个队列 q其中每个元素是二叉树节点指针。将根节点放入队列 q 中。初始化一个空的数组 ret用于存储每一层的最大值。进入主循环该循环用于遍历二叉树的每一层。 a. 初始化一个变量 m 为 INT_MIN用于记录当前层的最大值。 b. 获取当前队列的大小即当前层的节点数。 c. 遍历当前层的每个节点 弹出队列的首元素即最左边的节点。更新 m取 m 和当前节点值的较大值。如果节点有左子节点将左子节点加入队列 q。如果节点有右子节点将右子节点加入队列 q。 d. 将 m 添加到数组 ret 中。 返回最终的数组 ret其中包含了每一层的最大值。
代码
/*** 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:vectorint largestValues(TreeNode* root) {queueTreeNode* q;vectorint ret;if(!root) return ret;q.push(root);while(q.size()){int mINT_MIN;int nq.size();for(int i0;in;i){auto tq.front();q.pop();mmax(m,t-val);if(t-left) q.push(t-left);if(t-right) q.push(t-right);}ret.push_back(m);}return ret;}
};
