103. Binary Tree Zigzag Level Order Traversal

[zeikar]

Problem link

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

Problem Summary

이진 트리가 주어질 때 레벨 별로 지그재그 하면서 출력하는 문제

Solution

레벨별로 맵을 만들고 순서에 맞게 집어넣으면 된다. 일반 bfs 탐색을 약간 변형하면 됨

Source Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        queue = deque()
        if root:
            queue.append([root, 0])
        result = defaultdict(deque)

        while queue:
            c = queue.popleft()
            [node, level] = c
            if level % 2 == 0:
                result[level].append(node.val)
            else:
                result[level].appendleft(node.val)

            if node.left:
                queue.append([node.left, level + 1])
            if node.right:
                queue.append([node.right, level + 1])

        return [list(v) for v in result.values()]