Leetcode 103: Binary Tree Zigzag Level Order Traversal

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

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 

Code

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

from collections import *

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        q = deque()
        q.append((root, 1))
        
        res = []
        while q:
            tup = q.popleft()
            n, l = tup[0], tup[1]
            if n is not None:
                if len(res) < l:
                    res.append([])
                if l % 2:
                    res[l-1].append(n.val)
                else:
                    res[l-1].insert(0, n.val)
                q.append((n.left, l+1))
                q.append((n.right, l+1))
        
        return res

 

Idea

Use BFS to traverse nodes. Note that there may be one performance issue in my code: at line 29, left appending new element to a list may cause the whole list being copied again. We can pre-allocate a list for nodes in the same depth when `len(res) < l` by using: `res.append([0]*(len(q)+1))`.