N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
思路：
我们首先判断根节点是否为空，若为空则直接返回空列表。
否则，我们创建一个队列 q，初始时将根节点加入队列。
当队列不为空时，我们循环以下操作：
- 创建一个空列表 list，用于存放当前层的节点值。
- 对于队列中的每个节点，将其值加入 list中，并将其子节点加入队列。
- 将 list加入结果列表 ret。
最后返回结果列表 ret。
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null) {
return ret;
}
//创建队列 先进先出特性
Queue<Node> queue = new ArrayDeque<>();
//将root放进队列中
queue.offer(root);
while(!queue.isEmpty()) {
//计算此时queue里面的大小
int n = queue.size();
//用于存储每层节点数量
List<Integer> list = new ArrayList<>();
while(n != 0) {
Node cur = queue.poll();
list.add(cur.val);
//将结点的孩子带进队列中
for(Node x :cur.children) {
queue.offer(x);
}
n--;
}
//添加结果
ret.add(list);
}
return ret;
}
}二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
思路：
为了实现锯齿形层序遍历，需要在层序遍历的基础上增加一个标志位 i，用于标记当前层的层数。如果 i 为奇数，则当前层的节点值按照从左到右的顺序存入结果数组 ret中；如果 i为偶数，则当前层的节点值按照从右到左的顺序存入结果数组 ret中。
右到左的顺序：借助容器Collections的reverse函数反转
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null) return ret;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
int i = 1;
while(!q.isEmpty()) {
int n = q.size();
ArrayList<Integer> list = new ArrayList<>();
while(n-- != 0) {
TreeNode cur = q.poll();
list.add(cur.val);
if(cur.left != null) {
q.offer(cur.left);
}
if(cur.right != null) {
q.offer(cur.right);
}
}
if(i++ % 2 == 0) Collections.reverse(list);
ret.add(list);
}
return ret;
}
}二叉树最大宽度
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
此题求二叉树所有层的最大宽度，比较直观的方法是求出每一层的宽度，然后求出最大值。求每一层的宽度时，因为两端点间的 null 节点也需要计入宽度，因此可以对节点进行编号。
一个编号为 index 的左子节点的编号记为 2×index，右子节点的编号记为 2×index+1，计算每层宽度时，用每层节点的最大编号减去最小编号再加 1 即为宽度。
那么我们通过编号就可以计算同层中两个节点直接的距离了。
对于编号的存储，使用JDK内置的Pair对象
具体细节看代码：
class Solution {
public int widthOfBinaryTree(TreeNode root) {
//存储pair 第一个值为node ，第二个值为它的编号
List<Pair<TreeNode,Integer>> q = new ArrayList<>();
//先加入第一个节点
q.add(new Pair<TreeNode,Integer>(root,1));
//记录最终结果
int ret = 0;
while(!q.isEmpty()) {
//记录每层的最大宽度
//第一个位置
Pair<TreeNode,Integer> t1 = q.get(0);
//最后一个位置
Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
//更新结果
ret = Math.max(ret,t2.getValue() - t1.getValue()+1);
//创建新的q 保证每次记录的都是一层结果
List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
for(Pair<TreeNode,Integer> t : q) {
TreeNode cur = t.getKey();
if(cur.left != null) {
tmp.add(new Pair<TreeNode,Integer>(cur.left,t.getValue()*2));
}
if(cur.right != null) {
tmp.add(new Pair<TreeNode,Integer>(cur.right,t.getValue()*2 + 1));
}
}
//更新结果 让q 等于自己的下一层
q = tmp;
}
return ret;
}
}在每个树行中找最大值
给定一棵二叉树的根节点
root，请找出该二叉树中每一层的最大值。
使用
BFS进行层序遍历，单次BFS逻辑将整一层的元素进行出队，维护当前层的最大值，并将最大值加入答案。
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null) return ret;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
int max = Integer.MIN_VALUE;
while(!q.isEmpty()) {
int n = q.size();
while(n-- != 0) {
TreeNode cur = q.poll();
max = Math.max(max,cur.val);
if(cur.left != null) q.offer(cur.left);
if(cur.right != null) q.offer(cur.right);
}
ret.add(max);
max = Integer.MIN_VALUE;
}
return ret;
}
}