# 0103. Binary Tree Zigzag Level Order Traversal

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

## Description

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).

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)

```
**Input:** root = [3,9,20,null,null,15,7]
**Output:** [[3],[20,9],[15,7]]
```

**Example 2:**

```
**Input:** root = [1]
**Output:** [[1]]
```

**Example 3:**

```
**Input:** root = []
**Output:** []
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 2000]`.
* `-100 <= Node.val <= 100`

## ac1: DFS

* interchange of List and LinkedList

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(res, root, 0);
        return res;
    }
    private void helper(List<List<Integer>> res, TreeNode root, int level){
        if (root == null) return;

        if (res.size() <= level) res.add(new LinkedList<Integer>());

        if (level % 2 == 0) {
            res.get(level).add(root.val);
        } else {
            ((LinkedList<Integer>)res.get(level)).addFirst(root.val);
        }

        helper(res, root.left, level+1);
        helper(res, root.right, level+1);
    }
}
```

## ac2: BFS
