剑指 Offer 32 - III. 从上到下打印二叉树 III (opens new window)

1.层序遍历+列表容器翻转

分析：使用双端队列实现层序遍历。每层节点按照从左向右的顺序读取，然后根据奇偶层来决定是否需要对列表进行分层。Collections.reverse(list)

下面给出两种使用双端队列实现层序遍历的写法：

1.1保存每层遍历的最后节点

last保存当前队列的最后一个节点，next保存当前这一层的最后一个节点。

当前节点node搜索到next层最后节点时，将next更新为last。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
         Deque<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root==null) return list;
        List<Integer> curr=new ArrayList<>();
        queue.offerLast(root);
        TreeNode next=root,last=root;
        int reverse=-1;
        while(queue.size()!=0){
            TreeNode node=queue.pollFirst();
            curr.add(node.val);
            
            if(node.left!=null){
                queue.offerLast(node.left);
                last=node.left;
            }
            if(node.right!=null){
                queue.offerLast(node.right);
                last=node.right;
            }
            if(node==next){
                if(reverse==1) Collections.reverse(curr);
                list.add(new ArrayList<>(curr));
                curr.clear();
                next=last;
                reverse=-reverse;
            }
        }
        return list;
    }
}

1.2for循环遍历一层的节点

每次遍历一层的节点，for循环初始化拿到当前这层的节点数目。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            if(res.size() % 2 == 1) Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
}