1. N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
树的高度不会超过 1000
树的节点总数在 [0, 104] 之间
算法思路: 这个其实就是非常经典的BFS, 可以根据队列来进行层序遍历, 先让根节点进入队列, 然后执行出队列操作, 出队列的次数就是当前队列中元素的个数, 出队列操作首先将当前节点的保存下来, 然后pop, 并且记录val, 将他的孩子节点入队列.
/*
// 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;
}
};
*/
//1.头节点进队列, 队列不为空循环
//2.提取第一个队列元素, pop掉, 孩子入队列
//3.每次计算一下队列的节点个数, 进行几次的pop操作
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*> q;
vector<vector<int>> ret;
if(root == nullptr) return ret;
q.push(root);
while(q.size())
{
vector<int> tmp;
int sz = q.size();
for(int i = 0; i < sz; i++)
{
Node* front = q.front();
q.pop();
tmp.push_back(front->val);
for(auto& ch : front->children)
q.push(ch);
}
ret.push_back(tmp);
}
return ret;
}
};
2. 在每行中找出最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：
输入: root = [1,2,3]
输出: [1,3]
提示：
二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1
算法思路
依旧是利用层序遍历，但是这⼀次队列里面不单单存结点信息，并且还存储当前结如果在数组中存储所对应的下标（在我们学习数据结构 - 堆的时候，计算左右孩⼦的⽅式）。这样我们计算每⼀层宽度的时候，无需考虑空节点，只需将当层结点的左右结点的标相减再加 1 即可。但是，这里有个细节问题：如果⼆叉树的层数非常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为
• 我们数据的存储是⼀个环形的结构；
• 并且题目说明，数据的范围在 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:
vector<int> largestValues(TreeNode* root) {
vector<int> ret;
if(root == nullptr) return ret;
list<TreeNode*> lt;
lt.push_back(root);
while(lt.size())
{
int k = INT_MIN;
int sz = lt.size();
for(int i = 0; i < sz; i++)
{
TreeNode* front = lt.front();
lt.pop_front();
k = max(k,front->val);
if(front->left) lt.push_back(front->left);
if(front->right) lt.push_back(front->right);
}
ret.push_back(k);
}
return ret;
}
};
完