淄博做网站的公司都有哪些,正规的网站建设工作室,做夜场网站,工厂网站建设一、二叉树的层序遍历
. - 力扣#xff08;LeetCode#xff09; 该题的层序遍历和以往不同的是需要一层一层去遍历#xff0c;每一次while循环都要知道在队列中节点的个数#xff0c;然后用一个for循环将该层节点走完了再走下一层
class Solution {
public:vectorvec…
一、二叉树的层序遍历
. - 力扣LeetCode 该题的层序遍历和以往不同的是需要一层一层去遍历每一次while循环都要知道在队列中节点的个数然后用一个for循环将该层节点走完了再走下一层
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint ret;queueTreeNode* q;if(rootnullptr) return ret;q.push(root);while(!q.empty()){int szq.size();//帮助我们控制一层一层出 因为上一层出完下一层已经进去了vectorint path;//统计结果for(int i0;isz;i){TreeNode*tq.front();q.pop();path.push_back(t-val);if(t-left) q.push(t-left);if(t-right) q.push(t-right);}ret.push_back(path);;}return ret;}
}; 二、N叉树的层序遍历
. - 力扣LeetCode class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ret;//记录最终的返回结果if(rootnullptr) return ret;queueNode* q;//层序遍历所需要的队列q.push(root);//先将根节点插入进去while(!q.empty()) //因为统计的是每层所以我们没进去一次就要去统计一层。{int szq.size();//pop根节点的同时让他的孩子入队 //将左右孩子入队vectorint path;//记录每层的结果for(int i0;isz;i){Node* tq.front();q.pop();path.push_back(t-val);//开始让后面的节点入队for(Node* child:t-children) if(child!nullptr) q.push(child);}ret.push_back(path);}return ret;}
};
三、二叉树的锯齿形层序遍历
. - 力扣LeetCode 设置一个变量编辑层数单层的不处理双层的将path数组进行翻转
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root){vectorvectorint ret;//帮助我们记录要返回的数组queueTreeNode* q;//层序遍历需要的队列if(rootnullptr) return ret;q.push(root);int k1;//标记位while(!q.empty()){int szq.size();vectorint path;//记录要插入的结果for(int i0;isz;i){TreeNode*tq.front();//删除前拿到队头节点q.pop();path.push_back(t-val);//将结果插入进去if(t-left) q.push(t-left);if(t-right) q.push(t-right); }if(k%20) reverse(path.begin(),path.end());k;ret.push_back(path);}return ret;}
};
四、每个树行中找最大值
. - 力扣LeetCode 层序遍历的时候更新一下最大值即可
class Solution {
public:vectorint largestValues(TreeNode* root) {vectorint ret;if(rootnullptr) return ret;queueTreeNode* q;q.push(root);while(!q.empty()){size_t nq.size();//统计当前层int tempINT_MIN;for(size_t i0;in;i){TreeNode*tq.front();q.pop();tempmax(temp,t-val);//更新最大值//将孩子进队列if(t-left) q.push(t-left);if(t-right) q.push(t-right);}ret.emplace_back(temp);}return ret;}
};
五、二叉树的最大宽度非常经典
. - 力扣LeetCode 细节1下标可能溢出
关键是这里借助无符号整型在溢出的时候自动根据32位或者64位取模。
细节2利用数组的存储方式给节点编号移动赋值右值引用提高效率 用vector模拟queue 把孩子和其对应的下标存在数组中每一层处理完再进行移动赋值。
class Solution {
public:typedef pairTreeNode*,unsigned int PTU;int widthOfBinaryTree(TreeNode* root) {//用队列 直接连空节点也丢 超时//用数组模拟vectorPTU q;//用数组来模拟队列q.emplace_back(root,1);unsigned int ret1; //减掉之后不会影响结果while(!q.empty()){//先更新一下长度auto[x1,y1]q[0];auto[x2,y2]q.back();retmax(ret,y2-y11);//用一个新的数组入队vectorPTU temp;//用数组来模拟队列//让下一层进队列for(auto[x,y]:q){if(x-left) temp.emplace_back(x-left,y*2); //插入pair类型可以体现出emplace_back//和push_back的区别 push_back({x-left,y*2})if(x-right) temp.emplace_back(x-right,y*21);}//更新一个新的数组qmove(temp); //移动赋值 窃取资源 效率更高}return ret;}
};
