103. Binary Tree Zigzag Level Order Traversal (Medium)

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solutions

class Solution {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

        if (root == null) {
            return ans;
        }

        int maxDepth = maxDepth(root);

        // For different layer, allocate an ArrayList to hold the values.
        for (int i = 0; i < maxDepth; i++) {
            ans.add(new ArrayList<>());
        }

        recurse(root, 0, ans);

        // To form a zigzag sequence, reverse elements of even level
        for (int i = 0; i < ans.size(); i++) {
            if (i % 2 == 1) {
                Collections.reverse(ans.get(i));
            }
        }

        return ans;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;

        return Math.max(left, right);
    }

    private void recurse(TreeNode root, int depth, List<List<Integer>> ans) {
        if (root == null) {
            return;
        }

        // Apply pre-order visiting method such that values stored in each layer list
        // are arranged in the order from left to right.

        ans.get(depth).add(root.val);

        recurse(root.left, depth + 1, ans);
        recurse(root.right, depth + 1, ans);
    }
}

Incorrect Solutions

References