/**
* 103. 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]
* ]
*/
See the code here at github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trees/ZigZagTraversal.java
Observation: The code is interesting in that it asking for traversal from top to bottom while changing the direction of travel at each level. We can do a regular level order traversal using a queue and every time we change levels were invert the direction in which items are added to the list for that level. Changing the direction in list insertion is simple, when traversing left add to begging (addFirst). When traversing right add to end (addLast).
Here is the code:
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
boolean traverse_left = false;
List<List<Integer>> arr = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
queue.add(null);
LinkedList<Integer> currentLevel = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
if (traverse_left) {
currentLevel.addFirst(node.val);
} else {
currentLevel.addLast(node.val);
}
} else {
arr.add(currentLevel);
currentLevel = new LinkedList<>();
traverse_left = !traverse_left;
if (!queue.isEmpty()) {
queue.add(null);
}
}
if (null != node && node.left != null) {
queue.add(node.left);
}
if (null != node && node.right != null) {
queue.add(node.right);
}
}
return arr;
}