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++) {
}

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.

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