思路一：
加了一句：
if(res.size() % 2 == 1) Collections.reverse(tmp);
如果res.size()为奇数，当前层为偶数，反转tmp之后再存入res。
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if(root == null) return new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(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.offer(node.left); if(node.right != null) queue.offer(node.right); } if(res.size() % 2 == 1) Collections.reverse(tmp); res.add(tmp); } return res; } }
思路二：双端队列
偶数层的时候添加到队列头部而不是尾部，实现反转。
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if(root == null) return new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ LinkedList<Integer> tmp = new LinkedList<>(); for(int i = queue.size(); i > 0; i--){ TreeNode node = queue.poll(); if(res.size() % 2 == 0) tmp.addLast(node.val); // 奇数层 -> 队列头部 else tmp.addFirst(node.val); // 偶数层 -> 队列尾部 if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } res.add(tmp); } return res; } }
剑指 Offer 32 - III. 从上到下打印二叉树 III
原文：https://www.cnblogs.com/deerlet/p/14606506.html