Binary Tree Zigzag Level Order Traversal

Problem Id: 103 Difficulty: Medium Tag: Stack Tag: Tree Tag: Breadth-first Search


Intuition

This problem is based on basic BFS, with one thing changed.

This could be solved by just doing the standard BFS, while recording the level of each node. And in the end, reverse the level whose depth % 2 == 1.

Solution


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


class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        queue = deque([[root, 0]])

        while queue:
            node, level = queue.popleft()
            if node is None:
                continue
            if len(ans) <= level:
                ans.append([])
            ans[level].append(node.val)
            queue.append([node.left, level + 1])
            queue.append([node.right, level + 1])
        for i in range(1, len(ans), 2):
            ans[i].reverse()
        return ans