JZ77 之字形打印二叉树

1.题目描述

2.解题思路

拿到这个题目，首先就发现这个题目和二叉树层序遍历非常像，但是存在区别，二叉树层序遍历是按照“从上到下，从左到右”的顺序一层层进行的。但是这个题目要求奇数层从左往右，偶数层从右往左。函数返回的结果是一个ArrayList<ArrayList>的对象，所以要考虑对偶数层次的遍历结果做一个反转，再add到返回的ArrayList里面。
反转的实现我自己的思路是这样的，通过一个队列和一个栈，偶数层的层序遍历结果就将其入栈再add进去，层次数用一个boolean标记isEven来实现。但是这个方法不算很优雅，而且需要一个栈和一个队列，所需的额外空间变多了。
然后看了下别人利用Deque的解法，深感巧妙，因为反转实际上就是输入顺序与输出顺序相反，那从队列一端入队，再从同一端出队是不是也可以？而且在某一层操作全部完成之前，不会对下一层做操作，可以很容易地区分不同层次，而不需要使用标记变量或者哨兵。那么使用双端队列，Deque可以实现这一操作，具体来说就是：对奇数层，将其按照普通层序遍历的规则遍历，从队头出队，下一层的结点按照从左往右的顺序从队列尾端插入。对偶数层，则从队尾出队，下一层结点按照从右往左的顺序从队头插入。

3.代码实现

import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*//*利用双端队列的特性*/
public class Solution {public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {Deque <TreeNode> deque = new LinkedList<>();ArrayList<ArrayList<Integer> > ret = new ArrayList<>();//当root结点不为空时，将其入队if(pRoot != null) deque.offerLast(pRoot);while(!deque.isEmpty()) {// 打印奇数层//每个tmp存放一层的输出结果ArrayList <Integer> tmp = new ArrayList<>();//根据当前层结点数量确定操作for(int i = deque.size(); i > 0; i--) {// 从左向右输出，从队首出队TreeNode node = deque.removeFirst();tmp.add(node.val);// 先左后右顺序在队尾加入下层节点，先判断是否空if(node.left != null) deque.offerLast(node.left);if(node.right != null) deque.offerLast(node.right);}//把当前层的结果放到ret里ret.add(tmp);// 若队列为空说明树已经遍历完了，为空则提前跳出if(deque.isEmpty()) break; // 打印偶数层tmp = new ArrayList<>();//根据当前层结点数量确定操作for(int i = deque.size(); i > 0; i--) {// 从右向左输出，从队尾出队TreeNode node = deque.removeLast();tmp.add(node.val);// 按先右后左顺序在队头加入下层节点if(node.right != null) deque.offerFirst(node.right);if(node.left != null) deque.offerFirst(node.left);}//把当前层的结果放到ret里ret.add(tmp);}return ret;}}