103. Binary Tree Zigzag Level Order Traversal

解法一

思路

We can use the iteration method in 102. We use a LinkedList to store ndoes on each level. We observe that the odd level traverse from left to right, and the right level traverse from right to left. So for even level, we always poll the head on LinkedList, and add their children from left to right to the end of the LinkedList. For odd level, we always remove the last element in the LinkedList, and add their from right to left to the head of the LinkedList.

代码

Class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root  == null) {
            return levels;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        int level = 0;
        while(!list.isEmpty()) {
            int length = list.size();
            levels.add(new ArrayList<Integer>());
            for (int i = 0; i < length; i++) {
                // Even level
                if (level % 2 == 0) {
                    TreeNode node = list.poll();
                    levels.get(level).add(node.val);
                    if (node.left != null) {
                        list.add(node.left);
                    }
                    if (node.right != null) {
                        list.add(node.right);
                    }
                }
                // Odd level
                else {
                    TreeNode node = list.removeLast();
                    levels.get(level).add(node.val);
                    if (node.right != null) {
                        list.addFirst(node.right);
                    }
                    if (node.left != null) {
                        list.addFirst(node.left);
                    }
                }
            }
            level++;
        }
        return levels;
    }
}