Friedrich Ewald My Personal Website

Leetcode: Binary tree zigzag level order traversal

Traverse a tree where the root node is given with a zig-zag level and return the values in a list with one entry per level. For example:

-->    3
    /     \
   9       5      <--
        /     \
-->    7       8

Returns: [[3], [5,9], [7,8]]
This can be achieved with the same BFS algorithm from before, with an additional introduction of a reverse boolean variable. If the order is reversed, the output values are prepended instead of appended. After each level, the reverse variable is toggled via reverse = not reverse.
from typing import List, Optional

# 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
  
  def __repr__(self) -> str:
    return f"{self.val}"


class Solution:
  def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
      return []
    
    res = []
    queue = [[root]]
    reverse = False
    
    while len(queue) > 0:
      itms = queue[0]
      res.append([])
      queue.append([])

      for item in itms:
        if not item:
          continue
        if reverse:
          # prepend
          res[-1] = [item.val] + res[-1]
        else:
          res[-1].append(item.val)
          
        queue[-1].append(item.left)
        queue[-1].append(item.right)

      if len(res[-1]) == 0:
        queue.pop()
      queue = queue[1:]
      # Toggle reverse for next level
      reverse = not reverse
    if len(res[-1]) == 0:
      res.pop()

    return res


if __name__ == '__main__':
  s = Solution().zigzagLevelOrder
  print(s(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))), [[3], [20,9], [15,7]])
  print(s(TreeNode(1)), [[1]])
  print(s(None), [])


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.