:orphan:

Binary Tree Zigzag Level Order Traversal
========================================

.. highlight:: none

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

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

|image1|

::


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

.. |image1| image:: https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg

.. highlight:: python

Pattern
-------
Tree, Breadth-First Search, Binary Tree

Solution
--------
The solution is the same as level order traversal, but reverse the order of the
values if the depth is odd, starting at 0. The reason we reverse the order of
the values instead of the order of the nodes is because then nodes added to the
next level will also be reversed.

Code
----

.. literalinclude:: ../problems/medium/binary-tree-zigzag-level-order-traversal/binary_tree_zigzag_level_order_traversal__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from binary_tree_zigzag_level_order_traversal__approach_1 import zigzagLevelOrder, TreeNode
>>> root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
>>> zigzagLevelOrder(root)
[[3], [20, 9], [15, 7]]
>>> zigzagLevelOrder(TreeNode(1))
[[1]]
>>> zigzagLevelOrder(None)
[]

Complexity
----------
| :math:`n` is the number of nodes in the binary tree
| Time: :math:`O(n)` — visit each node once
| Auxiliary Space: :math:`O(n)` — `next_level` holds one level of nodes, up to
:math:`O(n / 2)` for a full binary tree

.. autoclass:: binary_tree_zigzag_level_order_traversal__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: binary_tree_zigzag_level_order_traversal__approach_1.zigzagLevelOrder