今天全部是层序遍历！
- 102.二叉树的层序遍历
- 107.二叉树的层次遍历II
- 199.二叉树的右视图
- 637.二叉树的层平均值
- 429.N叉树的层序遍历
- 515.在每个树行中找最大值
- 116.填充每个节点的下一个右侧节点指针
- 117.填充每个节点的下一个右侧节点指针II
-
102.二叉树的层序遍历
我愿称之为最初的经典。两天前的文章已经详细分析过，在此就不再分析。在此处粘贴出本题的代码意在展示层序遍历的基本结构，后面的题目都是在此结构的基础上进行修改，因此可对照查看从而牢记此结构。
class Solution {
public List<List<Integer>> resultList = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun02(root);
return resultList;
}
public void checkFun02(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int levelSize = queue.size();
while(levelSize > 0){
TreeNode tempNode = queue.poll();
list.add(tempNode.val);
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
levelSize--;
}
resultList.add(list);
}
}
}
这是基础代码框架，后续题目的代码都是在此基础上进行修改得到的，我会在后续代码中以注释的方式来注明 后续题目中 根据题目的要求 需要在此框架的基础上作出修改的地方。
-
107.二叉树的层次遍历II
本题是在层序遍历的基础上，要求输出的顺序是自底向上。那其实就是在基础的层序遍历基础上，每层遍历完之后的结果加入到List链表的头节点处。完整代码如下：
class Solution { //Java
public List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
checkFun03(root);
return result;
}
public void checkFun03(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
List<Integer> curLevel = new ArrayList<>();
for(int i = 0; i < levelSize; i++){
TreeNode curNode = queue.poll();
curLevel.add(curNode.val);
if(curNode.left != null){
queue.add(curNode.left);
}
if(curNode.right != null){
queue.add(curNode.right);
}
}
result.add(0,curLevel); // Add the node of the current layer to the head of the linked list
}
}
}
-
199.二叉树的右视图
本题是要输出每一层的最右侧的元素。那就是在每层遍历到最后一个元素时，把该元素的值加入到结果集result中就好。
class Solution { // Java
List<Integer> result = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
findMostRightList(root);
return result;
}
public void findMostRightList(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
TreeNode rightMostNode = null;
while(levelSize > 0){
TreeNode currentNode = queue.poll();
rightMostNode = currentNode; // to locate the most right Node
if(currentNode.left != null) queue.add(currentNode.left);
if(currentNode.right != null) queue.add(currentNode.right);
levelSize--;
}
if(rightMostNode != null){
result.add(rightMostNode.val); // add the value to result
}
}
}
}
可以看到，我们是定义了一个叫做rightMostNode的变量/指针来记录每层的最右边的元素，逻辑是随着内层while循环的进行，rightMostNode会逐渐指向右边的元素，当内侧while循环结束时，rightMostNode所指向的就是最右边的元素，然后我们执行result.add()，就把值加入到集合中了。
-
637.二叉树的层平均值
本题是在层序遍历的过程中，记录每一层的节点 值的平均值，因此就需要求和，然后同时每层的元素个数levelSize也要记录，才方便后续求出平均值。完整代码如下：
class Solution { // Java
List<Double> result = new ArrayList<>();
public List<Double> averageOfLevels(TreeNode root) {
findAvg(root);
return result;
}
public void findAvg(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
Double levelSum = 0.0; // record the sum in a level
int levelNum = levelSize; // record the levelSize
while(levelSize > 0){ // for循环替代的是这个while循环
TreeNode cur = queue.poll();
levelSum += cur.val; // get sum
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
levelSize--;
}
Double avg = levelSum / levelNum; // get the average
result.add(avg) ;
}
}
}
代码的注释很清晰的记录了在基础结构上所做出的改动。其中值得说明的是，内层while循环可以被for循环完美替代，每一个层序遍历都是如此，而在本题中，使用for循环替代的好处是 可以不用定义一个levelNum来记录levelSize了，因为如果使用while循环的话，levelSize就变成了循环控制因素，就会变化；而使用for循环，levelSize就不会变。
for (int i = 0; i < levelSize; i++) { // 替代上述while循环的for循环代码
TreeNode cur = queue.poll();
levelSum += cur.val;
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
-
429.N叉树的层序遍历
这题就是把二叉树换成了N叉树，所以就是在遍历每个节点的后面，要把下一层节点加入到队列中时，把左子树、右子树 这部分的代码 替换成 一个for循环，循环遍历N叉树节点的子节点数组，然后把每个子节点都加入到队列。
class Solution { // Java
public List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> levelOrder(Node root) {
findLevelOrder(root);
return result;
}
public void findLevelOrder(Node root){
if(root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
List<Integer> levelList = new ArrayList<>();
while(levelSize > 0){
Node tempNode = queue.poll();
levelList.add(tempNode.val);
for(Node n : tempNode.children){ // add all children of Node to the queue
if(n != null) queue.add(n);
}
levelSize--;
}
result.add(levelList);
}
}
}
-
515.在每个树行中找最大值
本题也比较好想，遍历每层时，加入一个变量一直记录当前层的最大值，当一层遍历结束时，把最大值加入到结果集result中。完整代码如下：
class Solution {
public List<Integer> result = new ArrayList<>();
public List<Integer> largestValues(TreeNode root) {
findLargestValue(root);
return result;
}
public void findLargestValue(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
int largestNum = Integer.MIN_VALUE;
while(levelSize > 0){
TreeNode tempNode = queue.poll();
largestNum = Math.max(largestNum, tempNode.val); // record the largest number
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
levelSize--;
}
result.add(largestNum);
}
}
}
-
116.填充每个节点的下一个右侧节点指针
本题就是在处理每个节点时，把它的next指针指向右侧的节点。对此我们采用的一个较为巧妙的做法是把弹出的当前节点指向队列queue中的顶部节点queue.peek();这是因为我们的元素是按照从左到右逐渐加入的，所以正好 对于当前弹出的元素tempNode而言，他要指向的元素，也就是在二叉树中位于他同层右边一位的元素，就正好在队列顶部。另外需要说明的一点是，本题有个特殊处理，那就是每层最右边的元素没人可指，但好在他原本的next值就是null，因此不需要额外处理，只需处理前面 levelSize-1 个元素的next指针就好。
class Solution { //Java
public Node connect(Node root) {
connectNode(root);
return root;
}
public void connectNode(Node root){
if(root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
for(int i = 0; i < levelSize; i++){
Node tempNode = queue.poll();
if(i < levelSize - 1){ // 处理前levelSize-1个元素就好
tempNode.next = queue.peek(); // 队列顶端元素正好是下一个元素
}
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
}
}
}
}
-
117.填充每个节点的下一个右侧节点指针II
本题与上一题LeetCode编号116的基本一样，唯一区别就在于116题中给出的二叉树为完美二叉树，而117题（本题）是普通二叉树。但在层序遍历的代码上是一样的，这是因为我们把元素加入到队列中时，就是按照每层的顺序添加的，因此空位的地方自动就被忽略了，所以代码不需要修改即可直接使用。
总结
层序遍历最重要的还是框架。框架主体结构如下：
首先就是定义一个全局变量result来收集结果（大部分都需要收集结果，然后根据题目的要求可能是List<>，也可能是List<List<>>.
然后就是定义一个方法来解决主要逻辑：
因为有了全局变量来收集结果，所以一般参数只需传入根节点root就好。
方法内先判断是否为空 if(root == null) return;
然后创建队列Queue<TreeNode> queue = new LinkedList<>(); 队列不能用ArrayList。
紧接着把root放入队列中 queue.add(root); 此处用queue.offer(root);也行
然后是外层while循环 while(!queue.isEmpty()){ 循环体1 }
在循环体1中 首先要做的就是记录每层的大小levelSize，即当前层有几个节点。
然后根据需要可以创建一个数组/链表来收集本层信息。
所以 外层循环里所做事情的含义就是 对于每一层都要用到的信息可以提取到这里。例如levelSize就是用来记录每层的节点个数，List<Integer>就是用来记录每层的节点的值。
内层循环。
内层循环可以是while循环，用levelSize > 0来控制，但是每次循环后得levelSize-1。因此levelSize的值会随着循环的进行而变化。
内层循环也可以是for循环，用for(int i = 0, i < levelSize; i++){}来控制。好处就是levelSize不变。具体使用看本文前半部分第四题。
内层循环的内部逻辑则是需要根据题意来了，但大体框架是先做逻辑（例如把节点的值添加到集合中，又或者是求得节点的值之和...）；然后添加元素，对于二叉树基本都是
if(tempNode.left != null) queue.add(tempNode.left);
if(tempNode.right != null) queue.add(tempNode.right); 这两句。
稍微特殊点的就是那个N叉树，但是原理也是一样，都是遍历所有的子节点然后添加。
最后就是在内层循环结束后，但是外层循环结束前。
在这里的话就是 如果需要把当前层的结果作为一个集合收集起来，就需要用全局变量result来收集它。result.add(List);
