目录
1.n叉树的层序遍历
2.二叉树的锯齿形层序遍历
3.二叉树的最大宽度
4.在每个树行中找最大值
1.n叉树的层序遍历
429. N 叉树的层序遍历 - 力扣（LeetCode）
我们只需要把某个节点出队的时候把它的孩子节点添加进来即可。
出队的次数就是最开始队列内的节点个数。因此我们也需要实现把根节点入队。
这里我们每次出队之前还需要把这个节点内的val值记录，以便于最后存储到ret中
/*
// 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>> ret;if(root == nullptr)return ret;queue<Node*> q;q.push(root);while(q.size()){int n = q.size();vector<int> tmp;while(n){for(int i = 0; i < (q.front()->children).size(); i++){q.push(q.front()->children[i]);}tmp.push_back(q.front()->val);q.pop();n--;}ret.push_back(tmp);}return ret;}
};2.二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
这道题注意点不多，只需要把经典的层序遍历更改一点代码。
我们增加一个标记位即可，对应标记位来标识是否需要逆置数组。同时入栈的时候我们需要判断一下这个节点是不是不为空
/*** 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<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;queue<TreeNode*> q;if(root == nullptr)return ret;q.push(root);int flag = -1;while(q.size()){vector<int> tmp;int n = q.size();while(n){TreeNode* node = q.front();tmp.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);q.pop();n--;}if(flag > 0){reverse(tmp.begin(),tmp.end());ret.push_back(tmp);}else{ret.push_back(tmp);}flag = -flag;}return ret;}
};3.二叉树的最大宽度
662. 二叉树最大宽度 - 力扣（LeetCode）
对于这题，我们需要在队列中存储一个pair，里面既要有节点指针，也要有一个编号。
我们只需要把某一层最右侧的节点编号减去最左侧的，即可得出宽度。
（如果节点编号很大，会出现溢出，但是在本题我们不用担心，我们知道，我们的数据存储实际上是一个环，因此即使数据溢出，他们两个的差只要不超过这个环的大小，那么他们的差就是合法的，可以计算的。这题我们使用unsigned int 避免正负的影响，就不会出现问题了）
/*** 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) {vector<pair<TreeNode* , unsigned int>> q;unsigned int ret = 0;q.push_back({root,1});while(q.size()){//先更新这一层的宽度auto& [x1, y1] = q[0];auto& [x2, y2] = q.back();ret = max(ret, y2 - y1 + 1);vector<pair<TreeNode* , 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;}
};4.在每个树行中找最大值
515. 在每个树行中找最大值 - 力扣（LeetCode）
这题需要注意的点是节点里面的最小值是INT_MIN，我们把tmp的初始值初始为INT_MIN
/*** 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) {queue<TreeNode*> q;vector<int> ret;if(root == nullptr)return ret;q.push(root);while(q.size()){int tmp = INT_MIN;int n = q.size();while(n){TreeNode* node = q.front();q.pop();tmp = max(tmp, node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);n--;}ret.push_back(tmp);}return ret;}
};
