算法通过村第六关-树白银笔记|层次遍历

前言

提示：这个世界上的任何一次拥抱都是将以松手告终。 --约瑟夫·布罗茨基《悲伤与理智》

二叉树的层次遍历是一个非常简单的问题，但是很多人没有接触过，所以就认为很难，面试的时候当然就写不出来了，今天我们就重点通关层次遍历这个问题。

1. 层次遍历介绍

广度优先在面试中属于常考类型，整体来说属于简单次，但是很多人面试遇到了就放弃，真的很可惜。我们就看看它的难度在哪里。

广度优先又叫做层次遍历，基本过程如下：

层次遍历就是从根节点开始，先访问根节点的一层全部元素，在访问之后的一层，类似金字塔一样一层一层访问。我们可以看做就是从左到右的一层一层去遍历二叉树，先访问5，之后访问3的左右孩子4 和 6 ，之后再访问4 和 6的孩子1 2 和 7 8。最后得到结果【5，4，6，1，2，7，8】

这里的问题就变成了将遍历过的子孩子保存下来，比如访问4 的左右孩子1 和 2 的时候应该先存储，直到处理完20之后再处理。使用队列的话就可以解决上述问题。

看下过程图解：

1. 根节点入队 5
2. 然后 5 出队， 之后将 5 的左右孩子4 6入队，保存在队列中
3. 4 出队，将4 的左右孩子 1 2 入队
4. 之后 6 出队，将 6 的左右孩子 7 8 入队，保存在队列中
5. 最终 1 2 7 8 依次出队，此时都是叶子几点，只要出队就行了。

这个过程不复杂，如果将树的每层分开，是不是可以整活