目录
1. N叉树的层序遍历
题目链接：429. N 叉树的层序遍历 - 力扣（LeetCode）
题目展示：
题目分析：
层序遍历即可~仅需多加⼀个变量，用来记录每⼀层结点的个数就好了。
代码实现：
/*
// 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;
queue<Node*> q;
if(root==nullptr)
{
return ret;
}
q.push(root);
while(q.size())
{
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)//让下一层节点入队
{
if(child!=nullptr)
{
q.push(child);
}
}
}
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;
if(root==nullptr)
{
return ret;
}
queue<TreeNode*> q;
q.push(root);
int level=1;
while(q.size())
{
int sz=q.size();
vector<int> tmp;
for(int i=0;i<sz;i++)
{
auto t=q.front();
q.pop();
tmp.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
//判断是否需要逆序
if(level%2==0) reverse(tmp.begin(),tmp.end());
ret.push_back(tmp);
level++;
}
return ret;
}
};3. 二叉树最大宽度
题目链接：662. 二叉树最大宽度 - 力扣（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:
int widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode*,unsigned int>> q;
q.push_back({root,1});
unsigned int ret=0;
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）
题目展示：
题目分析：
代码实现：
/**
* 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> ret;
if(root==nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
while(q.size())
{
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);
}
ret.push_back(tmp);
}
return ret;
}
};