剑指 Offer 32 - III. 从上到下打印二叉树 III

  对于这种问题，我们第一个需要考虑的问题是：如何对二叉树进行层次遍历。可以使用队列来对二叉树进行层次遍历，先将根结点入队，然后进入while循环，每次出队一个节点进行操作，然后把它对应的左节点和右节点入队（注意顺序不能变）。

　　然后，我们第二个需要考虑的问题是：怎么样把遍历次数限制在一行内。如果我们不进行特殊处理的话，遍历的顺序是：3，9，20，15，7。 但是我们现在需要的是 [3] [20,9] [15,7]，也就是每次只能遍历一行。  为了解决这个问题，我们可以在 while循环中 加入一个 for循环，这样就可以把遍历限制在一行里。

            for(int i=q.size();i>0;i--){ //q.size()是初始化条件
                TreeNode p = q.poll();
                list.add(p.val); //对节点进行操作
                if(p.left!=null){
                    q.add(p.left);
                }
                if(p.right!=null){
                    q.add(p.right);
                }
            }

 　　接着，我们第三个需要考虑的问题是：如何反转list中的元素。我们根据题目要求，偶数次的遍历需要反着来。对于这个问题，我们可以用 Collections 的 reverse方法，使list中的元素逆转（注意List是一个接口，我们可以用 ArrayList实现类）。

class Solution {
    public List> levelOrder(TreeNode root) {
        int count=1;//从第一次遍历开始
        List> res = new ArrayList<>();
        Queue q = new LinkedList<>();
        if(root!=null){
            q.add(root); //根节点入队
        }
        while(!q.isEmpty()){
            List list = new ArrayList<>();
            for(int i=q.size();i>0;i--){ //限制遍历次数
                TreeNode p = q.poll();
                list.add(p.val);
                if(p.left!=null){
                    q.add(p.left);
                }
                if(p.right!=null){
                    q.add(p.right);
                }
            }
            if(count%2==0){
               Collections.reverse(list); //需要特殊处理的行
            }
            res.add(list);
            count++;
        }
        return res;
    }
}