队列+宽搜_429. N 叉树的层序遍历

队列+宽搜_429. N 叉树的层序遍历_二叉树最大宽度

429. N 叉树的层序遍历

定义一个队列q，将一层的节点入队，并记录节点个数。根据节点的个数，出队列，并将其孩子入队列。出完队列，队列当前剩余节点的个数就是下次出队列的次数。直到队列为空

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> re;queue<Node*> q;if(root==nullptr) return re;q.push(root);while(!q.empty()){int sz=q.size();//当前层结点个数vector<int>tmp; //存放当前层结点对应的值for(int i=0;i<sz;i++){Node*t=q.front();q.pop();tmp.push_back(t->val);for(Node*child:t->children) //入队当前节点孩子vector<Node*> children{if(child!=nullptr) q.push(child);}}re.push_back(tmp);}return re;}
};

662. 二叉树最大宽度

我们知道二叉树可以用用数组表示，定义根节点下标为1，它左孩子下标就是2，右孩子3.

所以 父母节点节点下标 i ,左孩子下标i*2 右孩子下标i*2+1。

1.存入队列中的元素类型为pair<TreeNode*,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 re=0;vector<pair<TreeNode*,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 tmp=y2-y1+1;re=max(re,tmp);//2.更新q队列的节点（换下一层）vector<pair<TreeNode*,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*2+1});}q=t;}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:vector<int> largestValues(TreeNode* root) {vector<int> re;if(root==nullptr) return re;queue<TreeNode*> q;q.push(root);while(!q.empty()){int sz=q.size();int tmp=INT_MIN;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);}re.push_back(tmp);}return re;}
};