Leetcode 103. Binary Tree Zigzag Level Order Traversal (Python)

Related Topic

Breadth-First-Search . Queue . Stack .

Description

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,null,null,15,7],

Sample I/O

Example 1

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

Methodology (three ways)

1. Use BFS to traversal the tree level by level. To append each level in zigzag order, if the current level nodes pop in left -> right order, then to append children nodes of each node should be in right -> left order; if the current level nodes pop in right->left order, then to append children nodes of each node should be in left -> right order. This is a straight forward answer. This method need two way appending, so we choose deque which allow appending to front and to end.
2. We can also Use BFS to append each level node to the res list, then we only need focus on dealing with res list. We iterate the res list, each element is a list as well. If index of the element is dividable by 2 then we reverse this list element.
3. We use stack, the only difference is stack only allow append to the end. So we need a tmp stack for each level to avoid the appending affect the original stack. Then we append the each level nodes based on the zigzag order. After iteration of each level we replace stack with tmp stack and continue.

Code1 (BFS Straight Forward Answer)

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        queue = collections.deque([root])
        res = []
        flag = True #left->right
        while queue:
            tmp = []
            for _ in range(len(queue)):
                if flag:
                    node = queue.popleft()
                    tmp.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                else:
                    node = queue.pop()
                    tmp.append(node.val)
                    if node.right:
                        queue.appendleft(node.right)
                    if node.left:
                        queue.appendleft(node.left)
            flag = not flag
            res.append(tmp)
        return res

BigO

We traversal all elements of the tree once so total time complexity is O(n)

Code2 (BFS Straight Dealing with Res)

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        queue=collections.deque([root])
        res = []
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return [arr[::-1] if i%2 != 0 else arr for i, arr in enumerate(res)]

BigO

We traversal all elements of the tree once so total time complexity is O(n)

Code3 (BFS Stack only)

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        res = []
        stack = [root]
        left = True # True: left->right,  False: right->left
        while stack:
            tmp = []
            tmp_stack=[]
            for _ in range(len(stack)):
                node = stack.pop()
                tmp.append(node.val)
                if left:
                    if node.left: tmp_stack.append(node.left)
                    if node.right: tmp_stack.append(node.right)
                else:
                    if node.right: tmp_stack.append(node.right)
                    if node.left: tmp_stack.append(node.left)
            res.append(tmp)
            stack = tmp_stack
            left = not left
        return res

BigO

We traversal all elements of the tree once so total time complexity is O(n)