按层次初始化/遍历二叉树

按层次遍历二叉树的程序网上一大把,但是自己就没真的自己亲手去实现过.导致当出现新的需求时,没法立刻写出代码来.
需求:按层次遍历二叉树,根节点为0层.偶数层从左到右输出,奇数层从右到左输出.每输出一层,就输出一个换行.

Kiss

开始拿到需求的时候,第一想法是用以前了解的方法,将节点压进队列,从队列头每弹出一个节点,就将该节点的儿子们压进队列结尾.
这里与单纯的按层次遍历的不同之处在于:

当时是想通过循环解决这两个不同,每层节点数是2^i.输出这么多节点后就换行,同时依据i的奇偶性决定打印顺序.
按道理来说应该也可以实现,只是需要小心翼翼地处理各种细节和边界,那时我被困扰了,没有写出来.
更优雅一些,其实可以添加标志位,碰到换行标志位就换行,碰到奇偶标志位就做相应的输出处理.
具体来说:

以上的流程之所以能够实现功能,是因为交替变换奇偶标志,并利用辅助栈进行倒序输出.
而换行标志每次都恰好放置在该层最后一个节点的末尾,因此能正确换行.

实现