Get Keys In Binary Tree Layer By

Get the list of keys in a given binary tree layer by layer in zig-zag order.

Examples

        5

      /    \

    3        8

  /   \        \

 1     4        11

the result is [5, 3, 8, 11, 4, 1]

Corner Cases

What if the binary tree is null? Return an empty list in this case.

How is the binary tree represented?

We use the level order traversal sequence with a special symbol "#" denoting the null node.

from collections import deque
class Solution(object):
  def zigZag(self, root):
    if not root:
      return []
    res = []
    queue = deque()
    queue.appendleft(root)
    flag = True
    while queue:
      size = len(queue)
      for i in range(size):
        if flag:
          cur = queue.popleft()
          if cur.right:
            queue.append(cur.right)
          if cur.left:
            queue.append(cur.left)
        else:
          cur = queue.pop()
          if cur.left:
            queue.appendleft(cur.left)
          if cur.right:
            queue.appendleft(cur.right)
        res.append(cur.val)
      flag = not flag
    return res