LeetCode #103 Binary Tree Zigzag Level Order Traversal

Posted on | Post modified | In , , , , , , , ,

Problem

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

Solution

Method: Breadth-First Search

Time Complexity: O(n)

Space Complexity:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        bag = [root]
        level_idx = 0
        ret = []

        while bag:
            level_idx += 1
            next_level_nodes = []
            level_nodes = []

            for node in bag:
                if node:
                    level_nodes.append(node.val)
                    next_level_nodes.append(node.left)
                    next_level_nodes.append(node.right)
                    
            if level_idx % 2 == 1:
                ret.append(level_nodes)
            else:
                ret.append(level_nodes[::-1])
            bag = next_level_nodes
        
        if ret[-1] == []:
            ret.pop()

        return ret