[数据结构与算法]从上到下打印二叉树III（入门算法14）——广度优先遍历

题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

示例：

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

解题思路：
首先，从上到下打印，六个字很精准地给我们定位了，要我们使用广度优先算法进行计算。
而广度优先算法的思路就是：整两个队列，一个队列用来按层放此时遍历到的节点，一个队列用来放这一层遍历到的节点的值。
最后，由于他奇数行要从左往右读取，偶数行要从右往左读取，所以，我们只需要在原有的一直从左往右读的基础上多定义一个变量flag，当flag等于奇数或者偶数的时候（自己定，我是在奇数的时候让他从右往左读取），我们就让此时读取到的那一行数据倒置即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> arrayList = new ArrayList<>();
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        //标记用,指示程序是要从左往右读还是从右往左读
        int flag = 0;
        //空树,直接返回arrayList
        if(root == null) return arrayList;
        //非空, 则将第一层的节点，也就是root放入链表
        list.add(root);
        while(!list.isEmpty()){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for(int i = list.size(); i > 0; i--){
                //弹出节点链表的节点
                TreeNode node = list.poll();
                temp.add(node.val);
                //有左右节点则添加到节点链表（从左到右添加下一层的所有节点）
                if(node.left != null)   list.add(node.left);
                if(node.right != null)  list.add(node.right);
            }
            //flag为奇数,表示从右往左读取,所有要把数组倒过来
            if(flag++ %2 != 0){
                int len = temp.size();
                for(int i = 0; i < len/2; i++){
                    int t = temp.get(i);
                    temp.set(i, temp.get(len-i-1));
                    temp.set(len-i-1, t);
                }
            }
            arrayList.add(temp);
        }
        return arrayList;
    }
}

力扣战绩：