宁波网站推广方法,天津网,outlook企业邮箱注册,化妆品公司网站模板队列这种数据结构大都服务于一个算法——宽搜#xff08;BFS#xff09;。宽搜还可以运用到二叉树、图、迷宫最短路径问题、拓扑排序等等
N叉数的层序遍历
N叉树的层序遍历 题目解析
给定一个 N 叉树#xff0c;返回其节点值的_层序遍历_。#xff08;即从左到右#…队列这种数据结构大都服务于一个算法——宽搜BFS。宽搜还可以运用到二叉树、图、迷宫最短路径问题、拓扑排序等等
N叉数的层序遍历
N叉树的层序遍历 题目解析
给定一个 N 叉树返回其节点值的_层序遍历_。即从左到右逐层遍历。树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。
算法原理
层序遍历BFS宽度优先遍历当我们遍历完 1、3、2、4时要回过头看拓展3的子节点情况。这一过程属于先进先出的——队列这一数据结构可以解决以二维数组的形式返回。
搞一个队列如果根节点不为空先让根节点入队。然后开始while循环当队列不空的时候把队头元素1拿出来让队头元素的子节点2、3、4入队。接着继续将队头元素拿出来让队头元素2的子节点5、6入队.接着将队头元素3拿出来7入队4拿出来8入队。。继续拿出5、6、7、8他们都没有子节点就直接拿出即可
·
这里还有一个问题在一次访问遍历节点时如果出现不同层的节点元素进入该怎样统计呢我们这里只需要设置一个变量统计元素个数。即当1进入队列时计数为1当1出队列时2、3、4进入。此时个数为3就令变量为3。第二层出完时。第三层四个元素已经全部进入令变量为4。
代码实现
/*
// 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 nullptr) return ret;q.push(root);while(q.size()){int sz q.size(); // 先求出本层元素的个数vectorint tmp; // 统计本层的节点for(int i 0; i sz; i){Node* t q.front(); //拿出队头元素q.pop();tmp.push_back(t-val); //将节点加入到最终返回的数组中for(Node* child : t-children) // 遍历它的子节点让下⼀层结点⼊队{if(child ! nullptr)q.push(child);}}ret.push_back(tmp);}return ret;}
};二叉树的锯齿形层序遍历
二叉树的锯齿形层序遍历 题目解析 算法原理
解法层序遍历在层序遍历的结果存到最终返回结果之前奇数行直接存入要返回的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) {vectorvectorint ret;if(root nullptr) return ret;queueTreeNode* q;q.push(root);int level 1;while(q.size()){int sz q.size();vectorint tmp;for(int i 0; i sz; i){auto t q.front();q.pop();tmp.push_back(t-val);if(t-left) q.push(t-left);if(t-right) q.push(t-right);}// 判断是否逆序if(level % 2 0) reverse(tmp.begin(), tmp.end());ret.push_back(tmp);level;}return ret;}
};二叉树最大宽度
二叉树最大宽度 题目解析
给你一棵二叉树的根节点 root 返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。 算法原理
解法一硬来层序遍历统计每⼀层的最⼤宽度我们优先想到的就是利⽤层序遍历把当前层的结点全部存在队列⾥⾯利⽤队列的⻓度来计算每⼀层的宽度统计出最⼤的宽度。但是由于空节点也是需要计算在内的。因此我们可以选择将空节点也存在队列⾥⾯。
当遍历到最后一层时最后一层宽度为7。可以定义一个empty统计null个数从最后一层第一个位置开始扫描遇到null节点1直至遇到下一个有效数字。停止计算出宽度。然后再将empty置空为0然后继续向后遍历因为后面没有真实数字节点所以最后一个null不计入宽度里。
但是这里会超时会有一种极端情况。将3000个节点平均分题中给的数据范围为3000如果还按照我们上述计算宽度的算法那么最后一层将达到21000这样是大大超出内存的。
解法二利用数组存储二叉树给节点编号树我们不仅有链式存储还有顺序存储。我们可以通过给二叉树节点编号通过公式计算给他的子节点编号两个公式区别就是头结点从1开始计数还是从0开始计数 创建一个队列此时队列里就不仅仅存储节点我们即存他的节点也存他的编号。计算宽度方法就是拿出这个队的队头拿出这个队的对尾下标相减1即可这样就不需要处理空节点了。有的容器只能访问队头不能访问队尾这对于计算宽度就有些麻烦我们可以用数组模拟队列 细节问题下标有可能溢出。再次回到解法一遇到的极端情况在那种情况下最后一层的最后一个节点编号为21500-1.这个数字是任何一个数据类型都存不下的。但是当我们相减之后算出最后结果也是正确的。因为我们的数据存储是一个环形存储我们最终计算的是距离绿色部分这个距离是不会溢出的所以结果是正确的。我们C用unsigned int存储就不会报错了
代码实现
/*** 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 ret 0;while(q.size()){// 先更新这⼀层的宽度auto [x1, y1] q[0];auto [x2, y2] q.back();ret max(ret, y2 - y1 1);// 让下⼀层进队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 * 2 1});}q tmp;}
return ret;}
};在每个树行中找最大值
在每个树行中找最大值 题目解析
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
算法原理
利用层序遍历统计出每一层的最大值。
代码实现
/*** 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) {vectorint ret;if(root nullptr) return ret;queueTreeNode* q;q.push(root);while(q.size()){int sz q.size();int tmp INT_MIN; //初始化为无穷小让数字与tmp比较for(int i 0; i sz; i){auto t q.front(); //拿出队头元素q.pop(); //干掉队头元素tmp max(tmp, t-val); //更新这一层最大值if(t-left) q.push(t-left); //让其子节点入队if(t-right) q.push(t-right);}ret.push_back(tmp);}return ret;}
};
