英文网站标题,国内工业设计网站,做国际网站阿里巴巴,深圳网站做的好的公司哪家好这篇博客是关于队列宽搜的几道题#xff0c;主要包括N叉树的层序遍历、二叉树的锯齿形层序遍历、二叉树最大宽度、在每个数行中找最大值。 class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ret;if(!root) … 这篇博客是关于队列宽搜的几道题主要包括N叉树的层序遍历、二叉树的锯齿形层序遍历、二叉树最大宽度、在每个数行中找最大值。 class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ret;if(!root) return ret;queueNode* q;q.push(root);while(q.size()){int num q.size(); //先求出本层的元素个数vectorint tmp; //统计本层的节点while(num--){Node* top q.front();q.pop();tmp.push_back(top-val);for(auto e : top-children){if(e ! nullptr)q.push(e);}}ret.push_back(tmp);}return ret;}
}; 题目分析这道题我们需要层序遍历需要借助一个队列实现首先将第一层节点放进队列然后出队列在出队列后把它的孩子节点都push到队列中再依次把这几个孩子节点出队列每一个节点出队列后都要马上把它的孩子节点push到队列。为了知道每层有几个节点在每一层出队列前需要统计队列里的元素个数。 class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorint ret;if(!root) return ret;queueTreeNode* q;q.push(root);int flag 1;while(q.size()){int sz q.size();vectorint tmp;for(int i 0 ; i sz ; i){TreeNode* top q.front();q.pop();tmp.push_back(top-val);if(top-left) q.push(top-left);if(top-right) q.push(top-right);}if(flag % 2 0){reverse(tmp.begin(), tmp.end());}ret.push_back(tmp);flag;}return ret;}
}; 题目分析仍然是使用队列来存放节点和上一题不同的是在得到偶数层的队列后需要将其逆序一下可以通过创建一个变量来判断奇偶层。 class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vectorpairTreeNode*,unsigned int queue;unsigned int ret 0;queue.push_back({root, 1});while(queue.size()){auto [x1, y1] queue[0];auto [x2, y2] queue.back();ret max(ret, y2 - y1 1);vectorpairTreeNode*,unsigned int tmp;for(auto [x, y] : queue){if(x-left) tmp.push_back({x-left, 2*y});if(x-right) tmp.push_back({x-right, 2*y 1}); }queue tmp;} return ret;}
}; 题目分析这道题我们可以使用数组存储二叉树的方式给节点编号数组的类型为pairTreeNode*,intint为这个节点的编号一层的两端节点编号相减1就是这层的宽度。 需要注意的是下标可能溢出所以不能用int存储节点编号而是用unsigned int 存储。 class Solution {
public:vectorint largestValues(TreeNode* root) {queueTreeNode* q;vectorint ret;if(!root) return ret;q.push(root);// ret.push_back(root-val);while(q.size()){int size q.size();int m INT_MIN;while(size--){TreeNode* top q.front();q.pop();m max(m, top-val);if(top-left) q.push(top-left);if(top-right) q.push(top-right);}ret.push_back(m);}return ret;}
}; 题目分析很简单利用层序遍历统计每一层的最大值。
