二叉树按层交替反向遍历

在二叉树的实现与分析一文中我详实地探索和实现了二叉树的按层遍历流程，这里我对按层遍历做一个小小的增强：按层交替反向遍历。为什么要思考这样的增强？其实，是因为前段时间有朋友问过我这样的问题，感觉挺不错的，所以挑出来单独剖析。这里我假设有下面这样的一颗二叉树

按层交替反向遍历意思是说：第一层输出顺序为50；第二层输出顺序为(60,45)；第三层输出顺序为(40,47,55,72)；第四层输出顺序为(80,30)。

下面我就深入浅出地分析与实现上述增强。在实现按层遍历的需求时，我选了常规FIFO队列来辅助编码。这里，我依然选择队列来实现，不过稍微有点不同的是这里我选择使用双端队列。那么，我们应该怎么样依赖双端队列来实现这个需求呢？我的实现思路为：一层放入对头，下一层放入对尾，交替操作，然后分别遍历对头元素和队尾元素，直至二叉树遍历结束。

1. 双端队列使用方法分析

基于上述思路，我们在编码时到底会使用到双端队列的哪些方法呢？由于需要在对头和队尾都插入数据，显然我们肯定使用到offerFirst()方法和offerLast()方法，使用这两个方法的原因：不管操作成功与否，都会返回，不会抛出异常。此外，我们会分别遍历对头和队尾元素，我们会取出对头和队尾元素，元素遍历结束之后并将其移除，因此，肯定会使用到peekFirst()方法和peekLast()方法，这两方法上榜的原因是：方法在队列为空时直接返回null，不会抛出异常，方便我们做空判断。不管是对头元素还是队尾元素，遍历结束之后都会将其移除，pollFirst()方法和pollLast()方法上榜也就在情理之中了。

2. 实现逻辑分析

首先我们将二叉树的根节点插入到双端队列对头，然后开始操作双端队列。对双端队列的操作，我分为了两部分

遍历对头

遍历对尾

2.1 遍历对头逻辑分析

遍历对头的处理逻辑如下

取出对头元素，如果元素不为空，则输出；

判断对头元素左孩子是否为空，不为空则将其插入对尾；

判断对头元素右孩子是否为空，不为空则将其插入对尾；

移除对头元素；

跳转到第1步。

操作过程如下图所示

2.2 遍历对尾逻辑分析

遍历对尾的处理流程如下

取出对尾元素，如果不为空，则输出；

判断对尾元素右孩子是否为空，不为空则插入对头；

判断对尾元素左孩子是否为空，不为空则插入对头；

移除对尾元素；

跳转到第1步。

操作过程如下图所示

整个分析过程真是枯燥！千言万语不如一句代码，借用一句洋文来形容就是"talk is cheap, show me your code"(说这话这老外，真是，粗暴的很！(^▽^))。代码实现片段如下

其实，我一直在思考，二叉树这种结构到底有什么使用场景？到底能用来组织什么样的数据？你有自己的答案吗？