103_Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

Level: medium

Tag: tree, breadth-first search

Question

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).

Example 1

Input: 
    3
   / \
  9  20
    /  \
   15   7

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

Idea (breadth-first search)

• For each level, find all the node value, append to the result as a list. [reverse the node values if it's in even level]

• Have a temporary list to store all the left and right child for all the node in the level.

Solution : breadth-first search

Time: $O(n)$

Space: $O(n)$

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        res = []
        if root == None:
            return res

        level = [root]
        # use 1 and -1 to denote odd and even level
        flag = 1
        while len(level) > 0:
            # For each level, find all the node value, append to the result as a list
            res.append([node.val for node in level][::flag])
            flag *= -1
            # a temporary list to store all the left and right child for all the node in the level
            temp = []
            # append left and right child if they are not None
            for node in level:
                if node.left != None:
                    temp.append(node.left)
                if node.right != None:
                    temp.append(node.right)
            level = temp

        return res