# Binary Tree Zigzag Level Order Traversal LeetCode Solution

## Problem Statement

Binary Tree Zigzag Level Order Traversal LeetCode Solution – Given the `root` of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between). ```Input: root = [3,9,20,null,null,15,7]
Output: [,[20,9],[15,7]]```

## Explanation

We carry out simple level-order traversal but reverse alternate levels before adding them to the ans.

In this problem, we need to traverse the binary tree level by level. When we see levels in a binary tree, we need to think about BFS, because it is its logic: it first traverses all neighbors, before we go deeper. Here we also need to change direction on each level as well. So, the algorithm is the following:

1. We create a queue, where we first put our root.
2. `result` is to keep the final result and `direction`, equal to `1` or `-1` or we can keep it as a boolean in the direction of traverse.
3. Then we start to traverse level by level: if we have `k` elements in queue currently, we remove them all and put their children instead. We continue to do this until our queue is empty. Meanwhile, we form `level` list and then add it to `result`, using correct direction and changing direction after.

## Code

### C++ Code for Binary Tree Zigzag Level Order Traversal

```class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
if (root == NULL) {
return vector<vector<int> > ();
}
vector<vector<int> > result;

queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
bool leftToRight = true;

while ( !nodesQueue.empty()) {
int size = nodesQueue.size();
vector<int> row(size);
for (int i = 0; i < size; i++) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();

// find position to fill node's value
int index = (leftToRight) ? i : (size - 1 - i);

row[index] = node->val;
if (node->left) {
nodesQueue.push(node->left);
}
if (node->right) {
nodesQueue.push(node->right);
}
}
// after this level
leftToRight = !leftToRight;
result.push_back(row);
}
return result;
}
};```

### Java Code for Binary Tree Zigzag Level Order Traversal

```public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> sol = new ArrayList<>();
travel(root, sol, 0);
return sol;
}

private void travel(TreeNode curr, List<List<Integer>> sol, int level)
{
if(curr == null) return;

if(sol.size() <= level)
{
}

List<Integer> collection  = sol.get(level);
if(level % 2 == 0) collection.add(curr.val);

travel(curr.left, sol, level + 1);
travel(curr.right, sol, level + 1);
}
}```

### Python Code for Binary Tree Zigzag Level Order Traversal

```class Solution:
def zigzagLevelOrder(self, root):
if not root: return []
queue = deque([root])
result, direction = [], 1

while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:  queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level[::direction])
direction *= (-1)
return result```

O(N)

O(N)

Translate »