[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

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

Still use BFS approach to traverse the given binary tree. Remember to reverse value order on odd level.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();

        Deque<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offerLast(root);

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> tmp = new LinkedList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pollFirst();
                if (level % 2 == 0) {
                    tmp.offerLast(node.val);
                } else {
                    tmp.offerFirst(node.val);
                }
                if (node.left != null) queue.offerLast(node.left);
                if (node.right != null) queue.offerLast(node.right);
            }

            result.add(tmp);

            level += 1;
        }

        return result;
    }
}

DFS solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        dfs(root, 0);
        return result;
    }

    void dfs(TreeNode node, int level) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(new LinkedList<>());
        }

        if (level % 2 == 0) {
            ((LinkedList<Integer>)result.get(level)).offerLast(node.val);
        } else {
            ((LinkedList<Integer>)result.get(level)).offerFirst(node.val);
        }

        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

Edited on 06/06/2021. Add the DFS solution

Edited on 02/18/2023. Replace with Java version BFS & DFS solution