[Leetcode/Python] Binary Tree Zigzag Level Order Traversal

Top Interview Questions 의 Medium Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

 

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

 

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]]:
        if not root: return root
        answer, curr_level, flag = [], [root], 1
        while curr_level:
            answer.append([node.val for node in curr_level][::flag])
            next_level = []
            for node in curr_level:
                if node.left: next_level.append(node.left)
                if node.right: next_level.append(node.right)
            curr_level = next_level[:]
            flag *= -1
                
        return answer

 

Binary Tree Level Order Traversal 이 문제에서 살짝 변형된 스타일의 문제입니다.

Binary Tree Level Order Traversal은 각 레벨의 노드 값들을 순서대로 담았다면, 본 문제에서는 매 레벨마다 담는 순서를 바꿉니다. 루트 노드(첫 레벨)를 하나의 리스트에 담은 후 다음 리스트에는 두번째 레벨의 노드 값들을 역순으로 담습니다.

그러기 위해서 flag라는 변수를 추가하여 매 루프마다 리스트 값들을 나열하는 순서를 바꿔줍니다.