网站我优化,视频网站不赚钱为什么还做,盘锦市建设局网站地址,关于美丽乡村建设的活动和网站429. N 叉树的层序遍历 定义一个队列q#xff0c;将一层的节点入队#xff0c;并记录节点个数。根据节点的个数#xff0c;出队列#xff0c;并将其孩子入队列。出完队列#xff0c;队列当前剩余节点的个数就是下次出队列的次数。直到队列为空 /*
// Definition for a Nod…429. N 叉树的层序遍历 定义一个队列q将一层的节点入队并记录节点个数。根据节点的个数出队列并将其孩子入队列。出完队列队列当前剩余节点的个数就是下次出队列的次数。直到队列为空 /*
// 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 re;queueNode* q;if(rootnullptr) return re;q.push(root);while(!q.empty()){int szq.size();//当前层结点个数vectorinttmp; //存放当前层结点对应的值for(int i0;isz;i){Node*tq.front();q.pop();tmp.push_back(t-val);for(Node*child:t-children) //入队当前节点孩子vectorNode* children{if(child!nullptr) q.push(child);}}re.push_back(tmp);}return re;}
};
662. 二叉树最大宽度 我们知道二叉树可以用用数组表示定义根节点下标为1它左孩子下标就是2右孩子3. 所以 父母节点节点下标 i ,左孩子下标i*2 右孩子下标i*21。 1.存入队列中的元素类型为pairTreeNode*,int也要把对应节点的下标传过去。 2.知道队列头节点的下标 尾节点的下标 : i尾 - i头 1 尾两节点的距离就是当前层最长的距离 3.算完当前层再把它们左右孩子入队列直到队列为空. /*** 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) {uint32_t re0;vectorpairTreeNode*,uint32_t q;q.push_back(make_pair(root,1));while(q.size()){//1.记录当前层的最大宽度auto[x1,y1]q[0];auto[x2,y2]q.back();uint32_t tmpy2-y11;remax(re,tmp);//2.更新q队列的节点换下一层vectorpairTreeNode*,uint32_t t;for(auto[x,y]:q){if(x-left) t.push_back({x-left,y*2});if(x-right) t.push_back({x-right,y*21});}qt;}return re;}
}; 用数组模拟队列便于找头尾节点。 出队父母节点入队其孩子节点。不在原数组q上进行另开数组t入队其孩子节点。入完后再把存有孩子节点的数组t复制到原数组q上减少数组出队列移动元素的时间。 515. 在每个树行中找最大值 遍历每一层把每一次的最大值找出来 /*** 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 re;if(rootnullptr) return re;queueTreeNode* q;q.push(root);while(!q.empty()){int szq.size();int tmpINT_MIN;for(int i0;isz;i){auto tq.front();q.pop();tmpmax(tmp,t-val);if(t-left)q.push(t-left);if(t-right)q.push(t-right);}re.push_back(tmp);}return re;}
};
