[99클럽 코테 스터디 15일차 TIL] LeetCode | 2415. Reverse Odd Levels of Binary Tree

15일차 BFS

Problem

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/

 

Sol

출처 : https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/

 

완전 이진 트리(perfect binary tree) 의 홀수 레벨에 있는 노드의 값을 reverse하는 문제

 

👀 Perfect Binary Tree

 

 " 모든 레벨이 꽉 차 있는 트리"

 

문제에서 주어진 완전 이진 트리는 모든 레벨의 노드가 꽉 차있는 Perfect한 트리였다. Full Binary Tree에서  + 모든 leaf node의  depth까지 같은 트리임을 말한다.

문제에도 잘 설명이 되어 있어서 몰라도 풀이에 어려움은 없었다. 

 

enumerate

Python 내장 함수로, iterable(반복 가능한) 객체를 인덱스와 함께 순회할 수 있도록 한다. 반복문에서 인덱스와 해당 항목을 동시에 사용할 수 있다. 문제를 해결하기 위해 노드 리스트와 reverse된 값을 업데이트할 때 사용하여 각 노드의 인덱스와 값을 함께 처리하였다.

 

 

---

✔ Answer

deque를 사용하여 BFS 형식으로 해결하였습니다. 

# 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

from collections import deque

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        # Queue for BFS
        queue = deque([root])
        level = 0
        
        while queue:
            level_size = len(queue)
            current_level_vals = []
            nodes = []
            
            for _ in range(level_size):
                node = queue.popleft()
                nodes.append(node)
                current_level_vals.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            # reverse Odd level
            if level % 2 == 1:
                current_level_vals.reverse()
                for i, node in enumerate(nodes):
                    node.val = current_level_vals[i]
                    
            
            level+=1
        
        return root

---

💬 DFS/BFS 문제를 5일정도 풀고있는데 deque도 익숙해지고 있고 재밌다. 공부한 걸 정리하면 좋으련만 그럼 뭔가 힘들어져서 오래 못할 것 같으니까 이렇게 가볍게 오래 해야지~