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:

**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

/**
 * 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