成都搭建企业网站,一造和一建哪个难度大,网站建设 移动端 和 PC端,移动互联网时代的信息安全与防护超星网课答案429. N 叉树的层序遍历 题目解析#xff1a;
根据题目分析#xff0c;可以看出题目要我们求的是N叉数的层序遍历#xff0c;就是把每层的放在一块#xff0c;最后把每层都输出出来即可#xff01;
算法分析#xff1a;
我们可以利用队列先进先出的特性进行求解#x…429. N 叉树的层序遍历 题目解析
根据题目分析可以看出题目要我们求的是N叉数的层序遍历就是把每层的放在一块最后把每层都输出出来即可
算法分析
我们可以利用队列先进先出的特性进行求解这里比层序遍历多了一个条件记录当前层有多少个节点然后只把当前层的节点出完即可就是一层一层的进行输出我们需要记录每层的节点的值所以我们应该使用一个vector存储每层的节点然后最终将每层的结点放到最终的vector中即可
代码
class Solution {
public:vectorvectorint levelOrder(Node* root){//定义一个队列用于进行出队的操作queueNode* q;vectorvectorintret;//首先判断给定的根节点是否为空为空的话直接结束if(rootnullptr){return ret;}//不为空q.push(root);//当队中一直存在元素时一直进行遍历即可while(q.size()){//统计出本层的节点个数//只需要进行出队len次即可完成本次的出队操作int lenq.size();for(int i0;ilen;i){Node*temq.front(); //队头元素q.pop();v.push_back(tem-val); //将本层节点的值进行放入到vector中for(Node* child:tem-children){//本次元素出队之后将其孩子进行入队操作if(child){q.push(child);}}}ret.push_back(v);}return ret;}
}; 103. 二叉树的锯齿形层序遍历 题目解析
根据题目分析我们可以得出题目要让我们第一次进行从左向右遍历第二层进行从右向左遍历如此往复返回最终遍历的结果
算法分析
对于本题还是和之前二叉树的变量一样只不过是多了一个条件而言相邻的每行的遍历顺序恰好相反所以我们可以设置一个flag变量用于标志何时进行逆置即可当flag满足逆置的条件时我们把本层结点的vector进行reverse即可
代码
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root){vectorvectorintret;queueTreeNode*q;if(rootnullptr){return ret;}int flag1;q.push(root);while(q.size()){int lenq.size();//奇数为从左向右偶数相反//直接全部使用从左向右对于偶数的情况我们只需要将得到的vector进行reverse然后再插入即可vectorintv;for(int i0;ilen;i){TreeNode*temq.front();q.pop();v.push_back(tem-val);//下一层元素进行入队//左右孩子入队列if(tem-left){q.push(tem-left);}if(tem-right){q.push(tem-right);}}if(flag-1){reverse(v.begin(),v.end());}ret.push_back(v);flag*-1;}return ret;}
};
662. 二叉树最大宽度 题目解析
根据题目分析我们可以得出题目要我们求出二叉树的最大宽度其中最大宽度的定义为最左和左右的非空节点之间的长度
算法分析
我们可以利用堆中下标的思想进行求解我们在堆那边有一个公式当根节点下标为0时左孩子下标为2*parent1,右孩子下标为左孩子1。当根节点为1时左孩子下标为2*parent,右孩子仍然是左孩子1根据下标的特性我们可以求出二叉树的最大宽度
代码
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;}}; 515. 在每个树行中找最大值 题目解析
根据题目简单的介绍我们可以得出题目要出的答案就是获取每层的最大值然后进行push到结果数组中即可
算法讲解
还是和N叉数的层序遍历一样我们还是需要记录的每层结点的个数只不过本次我们需要引进一个新的变量用于记录每层的最大值即可我们开始将此变量置为INT_MIN即可
代码
class Solution {
public:vectorint largestValues(TreeNode* root){queueTreeNode*q;vectorintret;if(rootnullptr){return ret;}q.push(root);//当队列不为空的时候一直进行循环即可while(q.size()){ int mINT_MIN;//求出本层的结点个数int lenq.size();for(int i0;ilen;i){TreeNode*temq.front();q.pop();if(tem-valm){mtem-val;}//把下一层的元素压入到队列中if(tem-left){q.push(tem-left);}if(tem-right){q.push(tem-right);}}ret.push_back(m);}return ret;}}; 至此本专题总结完毕有疑问的小伙伴可以在评论区进行讨论。
