Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).


For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7



return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

Starter code: # Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        

Solutions:
class Solution:

	def zigzagLevelOrder(self, root):
		if root == None:
			return []
		result = []
		queue = []
		queue.append([0, root])
		while len(queue) != 0:
			(level, temp) = queue.pop(0)
			if len(result) < level + 1:
				result.append([])
			if level % 2 == 0:
				result[level].append(temp.val)
			else:
				result[level].insert(0, temp.val)
			if temp.left:
				queue.append([level + 1, temp.left])
			if temp.right:
				queue.append([level + 1, temp.right])
		return result