@@ -0,0 +1,2617 @@
+package com.leetcode.trees;%0A%0Aimport java.util.*;%0A%0Aimport static org.junit.jupiter.api.Assertions.assertEquals;%0A%0A/**%0A * Level: Medium%0A * Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/%0A * Description:%0A * Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then%0A * right to left for the next level and alternate between).%0A *%0A * For example:%0A * Given binary tree %5B3,9,20,null,null,15,7%5D,%0A *     3%0A *    / %5C%0A *   9  20%0A *     /  %5C%0A *    15   7%0A * return its zigzag level order traversal as:%0A * %5B%0A *   %5B3%5D,%0A *   %5B20,9%5D,%0A *   %5B15,7%5D%0A * %5D%0A *%0A * @author rampatra%0A * @since 2019-08-11%0A */%0Apublic class BinaryTreeZigZagLevelOrderTraversal %7B%0A%0A    /**%0A     * Time Complexity:%0A     * Space Complexity:%0A     * Runtime: %3Ca href=%22https://leetcode.com/submissions/detail/250830618/%22%3E1 ms%3C/a%3E.%0A     *%0A     * @param root%0A     * @return%0A     */%0A    public static List%3CList%3CInteger%3E%3E zigzagLevelOrder(TreeNode root) %7B%0A%0A        int levelNo = 0;%0A        LinkedList%3CInteger%3E currLevel = new LinkedList%3C%3E();%0A        List%3CList%3CInteger%3E%3E levelOrderTraversal = new LinkedList%3C%3E();%0A%0A        if (root == null) %7B%0A            return levelOrderTraversal;%0A        %7D%0A%0A        Queue%3CTreeNode%3E queue = new LinkedList%3C%3E();%0A        queue.add(root);%0A        queue.add(null);%0A%0A        while (!queue.isEmpty()) %7B%0A%0A            TreeNode treeNode = queue.poll();%0A%0A            if (treeNode == null) %7B%0A                levelOrderTraversal.add(currLevel);%0A                currLevel = new LinkedList%3C%3E();%0A                levelNo++;%0A%0A                if (queue.size() %3E 0) %7B%0A                    queue.add(null);%0A                %7D%0A            %7D else %7B%0A                if (levelNo %25 2 == 0) %7B%0A                    currLevel.add(treeNode.val);%0A                %7D else %7B%0A                    currLevel.add(0, treeNode.val);%0A                %7D%0A                if (treeNode.left != null) queue.add(treeNode.left);%0A                if (treeNode.right != null) queue.add(treeNode.right);%0A            %7D%0A        %7D%0A%0A        return levelOrderTraversal;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        /*%0A            Binary Tree%0A%0A                1%0A               / %5C%0A              2   3%0A             / %5C%0A            4   5%0A         */%0A        TreeNode tree = new TreeNode(1);%0A        tree.left = new TreeNode(2);%0A        tree.right = new TreeNode(3);%0A        tree.left.left = new TreeNode(4);%0A        tree.left.right = new TreeNode(5);%0A%0A        assertEquals(%22%5B%5B1%5D, %5B3, 2%5D, %5B4, 5%5D%5D%22, zigzagLevelOrder(tree).toString());%0A        assertEquals(%22%5B%5D%22, zigzagLevelOrder(null).toString());%0A    %7D%0A%7D%0A

zigzag traversal: done