自己ac了一遍之后, 发现google排名靠前的少有Java版的实现, 这里贴上我自己的实现.
思路非常简单, 使用双端队列作为层次遍历的支持结构, 然后用一个布尔型变量控制下一层遍历是队头出还是队尾出.
public class Solution { /** * @param root: The root of binary tree. * @return: A list of lists of integer include * the zigzag level order traversal of its nodes' values */ public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if (root == null) { return res; } ArrayList<Integer> floor = new ArrayList<>(); Deque<TreeNode> deque = new ArrayDeque<>(); TreeNode last = root; deque.offer(root); boolean nextPoll = true; while (!deque.isEmpty()) { TreeNode temp = nextPoll? deque.poll(): deque.pollLast(); floor.add(temp.val); if (nextPoll) { if (temp.left != null) { deque.offer(temp.left); } if (temp.right != null) { deque.offer(temp.right); } } else { if (temp.right != null) { deque.offerFirst(temp.right); } if (temp.left != null) { deque.offerFirst(temp.left); } } if (last == temp) { res.add(floor); floor = new ArrayList<>(); last = nextPoll? deque.peek(): deque.peekLast(); nextPoll = !nextPoll; } } return res; } }