1.针对二叉树的宽度优先遍历

2.宽度优先遍历常使用队列结构

3.面试中，该类题目长对换行有所要求。

题目一：给定一棵二叉树的头节点head，请按照现在大家看到的这种格式打印

原理知识：

last----正在打印的当前行的最右节点。

nlast---表示下一行的最右节点。

假设每一层都做从左到右的宽度优先遍历，

如果发现遍历到last节点，说明该换行了。

换行之后，只要指定last=nlast,就可以下一行的打印过程。

一直重复这个动作，直到所有的节点都打印完毕。

现在就变成了如何正确更新last与nlast的问题。

让nlast一直追踪记录宽度优先队列中最新加入的节点即可。

因为最新加入的节点一定是，目前发现的这一行的下一行的，最右端的节点。

所以在当前行打印完毕时，nlast一定是下一行的最右的节点。

新建一个queue，另last-->节点1，放入queue，弹出节点1，并打印。

然后把节点1的孩子一次放入到queue中。

放入节点2时，令nlast=节点2,放入queue.

放入节点3时，令nlast=节点3，放入queue.

此时发现弹出的节点1与last相等。换行。

令last=nlast,也就是节点3.

现在需要从queue中弹出节点2，并打印完毕。

并让他的孩子节点4进入的queue中。同时让nlast=节点4.

从queue中弹出节点3，并打印。

再放入他的孩子节点5进入到queue 中，另nlast=节点5。

再放入节点3的孩子节点6，另nalst=节点6.

此时发现刚才弹出的节点3已经是last节点了。

所以，该换行了。

再另last=节点6，此时last=nlast。

last又重新更新成了下一行的最右的节点，

也就是说nlast始终记录着刚进入队列中的节点。

也就是一直记录着，目前出现最后一层的，最右的节点。

当某一节点走到last的时候，说明这一行打印完毕，需要打印换行。

接下来让当前的last=当前的nlast，正确的找到下一层最右的节点。

从而每次都能正确的完成换行这个动作。