二叉树的蛇形层次遍历(LeetCode.103)

题目

截图自LeetCode.103——二叉树的锯齿形层次遍历

解析

首先参考二叉树的层次遍历层次遍历二叉树（LeetCode--102二叉树的层次遍历）
同样的层次遍历方式，只是间隔一行的输出顺序改变而已。我们只需要增加控制需要反序的层输出逻辑即可。

代码

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new LinkedList<>();
    if(null == root){
        return res;
    }
    //定义标志当前层是否需要反序
    boolean reversed = false;
    //队列暂存层次遍历的节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        //当前层节点的个数
        int size = queue.size();
        //当前层输出结果，LinkedList可以基于头部和尾部插入
        LinkedList<Integer> l = new LinkedList<>();
        for(int i=0; i<size;++i){
            TreeNode n = queue.poll();
            //如果需要反序，节点插入到队列的头部。否则插入尾部。
            if(reversed){
                l.addFirst(n.val);
            }else{
                l.add(n.val); 
            }
            //下一层节点入队
            if(null != n.left){
                queue.add(n.left);
            }
            if(null != n.right){
                queue.add(n.right);
            }     
        }
        //每层遍历结束后，调整标志。交替正序和反序。
        reversed = !reversed;
        //保存结果
        res.add(l);
    }
    return res;
}