(Python3) - LeetCode (Medium) : 2415. Reverse Odd Levels of Binary Tree

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

level별 순회하는 bfs 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. deque선언 후 root를 넣어줍니다.

 

2. level 선언 후 0으로 초기화합니다.

📔 풀이과정

dq에 원소가 있는 동안 while loop로 다음을 진행합니다.1. 현재 레벨에서 순회가능한 node 수는 dq의 크기입니다. 따라서 dq의 크기만큼 for loop를 수행하며 넣을 수 있는 다음 왼쪽, 오른쪽 서브 트리의 노드들을 넣어줍니다.

 

2. 완전 이진 트리이므로 왼쪽과 오른쪽 서브 트리에는 말단을 제외하고 항상 원소가 존재합니다. 서브트리가 존재하면 dq에 원소들을 넣어주고, 다음 레벨이 홀수라면 원소들을 뒤집어 dq에 넣어주기 위해 해당 val들을 cur_level_values에 append해줍니다.

 

for문이 끝나면 dq에는 다음 레벨의 서브트리들이 원소로 저장되어 있습니다. 따라서 레벨이 홀수라면 dq의 크기만큼 loop를 수행하며 dq[i].val에 cur_level_values에 pop한 값을 넣어줍니다.

📔 정답 출력 | 반환

갱신된 root를 반환합니다.

---

📕 Code

📔 Python3

from collections import deque

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        dq = deque([root])
        level = 0
        while dq:
            cur_level_size = len(dq)
            cur_level_values = []
            level += 1

            for _ in range(cur_level_size):
                cur_node = dq.popleft()
                if cur_node.left and cur_node.right:
                    dq.append(cur_node.left)
                    dq.append(cur_node.right)
                    if level % 2 == 1:
                        cur_level_values.append(cur_node.left.val)
                        cur_level_values.append(cur_node.right.val)
            if level % 2 == 1:
                for i in range(len(dq)):
                    if cur_level_values:
                        dq[i].val = cur_level_values.pop()
        return root

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.