二叉树层序遍历登场
层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
果然看java还是很不爽，C++和python的代码简洁明了
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
//DFS--递归方式 public void checkFun01(TreeNode node, Integer deep) { if (node == null) return; deep++; if (resList.size() < deep) { //当层级增加时，list的Item也增加，利用list的索引值进行层级界定 List<Integer> item = new ArrayList<Integer>(); resList.add(item); } resList.get(deep - 1).add(node.val); checkFun01(node.left, deep); checkFun01(node.right, deep); }
//BFS--迭代方式--借助队列 public void checkFun02(TreeNode node) { if (node == null) return; Queue<TreeNode> que = new LinkedList<TreeNode>(); que.offer(node); while (!que.isEmpty()) { List<Integer> itemList = new ArrayList<Integer>(); int len = que.size(); while (len > 0) { TreeNode tmpNode = que.poll(); itemList.add(tmpNode.val); if (tmpNode.left != null) que.offer(tmpNode.left); if (tmpNode.right != null) que.offer(tmpNode.right); len--; } resList.add(itemList); } }
注意边界值的判断，如果一开始输入就是null我们需要加第一句话 如果是null 则立刻return
复习多态-QUEUE
Queue接口及其实现类（ArrayDeque和LinkedList）
Queue接口是collection的子接口，是以先进先出的方式排列元素
Deque接口实现双端队列，ArrayDeque和LinkedList是它的两个实现类
ArrayDeque类是可变数组的实现，不可存储null。LinkedList是线性表的实现，实现了线性表的所有操作，可存储null
PriorityDeque实现的是一种优先队列，优先队列中的元素顺序是根据元素的值排列的
下面程序演示了ArrayDeque类的使用，实现双端队列
————————————————
版权声明：本文为CSDN博主「nuist__NJUPT」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/nuist_NJUPT/article/details/116269208
102.二叉树的层序遍历
标准层序遍历
107.二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
solution： 层序遍历后翻转
199.二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
solution：返回每一层的最右边的节点放在list中
637.二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
solution:累加并除以每行个数
429.N叉树的层序遍历
利用for(Node j: temp.children)代替左右子树判断
515.在每个树行中找最大值
int max = Integer.MIN_VALUE;116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
111.二叉树的最小深度
226.翻转二叉树
递归法:先序遍历
迭代法：二叉树：听说递归能做的，栈也能做！ (opens new window)中给出了前中后序迭代方式的写法，所以本题可以很轻松的写出（中右左，栈的方法）
广度优先遍历： 层序遍历
101. 对称二叉树
考虑递归的方法，注意内外的区分
return searchnode(leftNode.left, rightNode.right) && searchnode(leftNode.right, rightNode.left);
以及需要考虑一些边界条件的判断