부부의 코딩 성장 일기

LeetCode 103(Binary Tree Zigzag Level Order Traversal, Python) 본문

Algorithm/LeetCode

LeetCode 103(Binary Tree Zigzag Level Order Traversal, Python)

펩시_콜라 2024. 2. 22. 19:00

1. 문제 링크

 

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

2. 문제 설명

  • binary tree의 root가 주어졌을 때, level 별로 zigzag 순서로 nodes의 값을 적재하여 반환
    • level 0에서 왼쪽 → 오른쪽으로 path를 적재했다면,
    • level 1에서는 오른쪽 → 왼쪽으로 path를 적재하는 것
  • 예를 들어 아래와 같은 tree가 있다고 할 때, 
    • root node가 있는 level에서는 3을 적재하고, 그 다음 level에서는 [20, 9]의 순서로
    • 그 다음 level에서는 반대로 [15,7]의 순서로 적재한다.
    • 결국 Input root = [3,9,20,null,null,15,7]이면, output = [[3],[20,9],[15,7]]이 된다.

 

3. 처음 풀이

  • 처음에 조금은 비효율적으로 접근했다. 
  • 우선 root, root.left, root.right를 path에 적재하는데, 
    • root에서 root.left, root.right로 갈 때 level이 한 개 증가하므로, 
    • root와 level을 인자로 받는 helper함수를 만들어서,
      • 우선은 모든 level이 왼→오의 방향으로 쌓이게 만든 뒤에
      • 나중에 for 문을 돌면서 홀수 층의 경우, list를 거꾸로 바꿔서 append했다.
  • 해당 풀이가 비효율적인 이유는
    • 한번 list에 쌓을 때 순서를 뒤집어가면서 하면 되는데, 굳이 다 만든 뒤에 뒤집기 때문.
# 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]]:

        path = {}
        
        def helper(root, level):
            if root is None:
                return 

            if level not in path:
                path[level] = [root.val]
            else:
                path[level] += [root.val]
            
            helper(root.left,level+1)
            helper(root.right,level+1)

        helper(root,0)
        output = []
        for index, i in enumerate(path.values()):
            if index % 2 == 1:
                output.append(i[::-1])
            else:
                output.append(i)
            
        return output

4. 다른 풀이

  • 많은 풀이에서 deque를 사용했다.
    • 이걸 사용하지 않고, 앞에 원소를 쌓거나, 그냥 append하거나 둘 중 하나로 해도 되긴 하는데, 시간 복잡도에서 이점이 있다고 한다.
  • deque는 collections 모듈(이건 leetcode에서 기본적으로 제공해준다.)의 함수이고 deque를 사용하면 리스트의 맨 앞에 원소를 추가하거나 제거할 때 O(1)의 시간복잡도를 가지므로 성능이 향상될 수 있다.
  • 추가로 나는 내가 익숙한 DFS 방식으로 했는데, BFS로 너비 우선탐색을 해야 레벨 순서를 쉽게 처리할 수 있다. 
  • 아래의 코드를 보면
    • 우선 root를 deque에 넣는 queue를 만들고, 
      • queue의 length만큼 for문을 돌리는데, 
      • queue에서 가장 왼쪽에 있는 node를 가져와서 해당 value를 append하고,
      • 만약 node.left가 존재하면, queue에 node.left를,
      • 만약 node.right가 존재한다면, queue에 node.right를 append한다.
    • 그다음 지그재그 순서를 가야 하므로, 
      • 만약 reverse = True이면, result에 level_values를 거꾸로 뒤집어서 append하고, 
      • reverse = False이면, 그대로 append한다음에 
      • result를 반환 
# 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 []

        result = []
        queue = deque([root])
        reverse = False

        while queue:
            level_values = []
            level_size = len(queue)

            for _ in range(level_size):
                node = queue.popleft()
                level_values.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            if reverse:
                result.append(level_values[::-1])
            else:
                result.append(level_values)

            reverse = not reverse

        return result

 

  • 위 풀이도 정리하다보니, 결국 또 [::-1]로 뒤집는게 나오는데 아래 코드처럼,
    • left, right인지에 따라, append(node.val)을 하거나, insert(0,node_val)을 해서 가장 왼쪽에 삽입을 하면 바로 list에 추가 가능하다.
# 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]]:
        res = []
        queue = deque([root])
        left_order = True
        while queue:
            level_res = []
            for _ in range(len(queue)):
                node = queue.popleft()
                if node:
                    if left_order:
                        level_res.append(node.val)
                    else:
                        level_res.insert(0, node.val)
                    queue.append(node.left)
                    queue.append(node.right)
            left_order = not left_order
            if level_res:
                res.append(level_res)
        return res

 

5. 배운 점 

  • BFS 방식에 익숙해지기