[bfs] deque로 treenode의 값 뒤바꾸기

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

 

examples and contraints

# 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
from typing import Optional

class Solution:

def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
return root

 

위가 기본으로 주어지는 코드였다.

문제는 단순히 이진트리 중 홀수번째 leaf들의 값을 뒤바꿔라였는데, 이와 별개로 몇가지 지식을 알아야했다.

 

타입 힌트 (Optional)

from typing import Optional

Python의 typing 모듈에서 제공하는 Optional은 값이 특정 타입이거나 None일 수 있음을 나타냅니다. Optional[TreeNode]는 TreeNode 객체이거나 None일 수 있음을 의미합니다. 이는 코드의 가독성을 높이고, 타입 체킹 도구가 코드의 일관성을 검사할 수 있도록 도와줍니다.

 

즉, TreeNode라는 객체가 들어간다는 말인데, 기본 코드에 예시로 나와있는 TreeNode를 보면, 한 TreeNode 객체에 val, left right값이 들어 갈 수 있다.

val 값은 node의 숫자값일 것이고, left와 right에는 또다른 TreeNode 객체가 마치 recursion 처럼 들어 갈 것이다!!

 

즉, reverseOddLevel(root)에서, root node 내에는 left와 right로써 node가 계속 있을 수 있다.

 

이러한 TreeNode구조에서 특정 depth들의 node를 탐색하려면, 결국 모든 node들을 모두 탐색하여야한다.

이를 위해 bfs와 dfs 중 한 방법을 택해야 하는데, 딱봐도 bfs가 적합하다고 느꼈다.

(목적은 같은 depth내의 node들의 값을 역순으로 바꾸는 것인데, 그들은 edge로 연결되어있지 않음)

 

그리고 bfs 구현을 위해서는 queue를 사용하는 것이 일반적인데, 그중에서도 효율이 좋은 deque를 사용하기로 했다.

 

덱 (Deque) 

deque는 collections 모듈에서 제공하는 자료구조로, 양방향 큐를 의미합니다. 이는 양쪽 끝에서 빠르고 효율적으로 삽입과 삭제를 수행할 수 있습니다. 주요 특징은 다음과 같습니다:

• 시간 복잡도: 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도를 가집니다.

from collections import deque

# 덱 생성
deque_list = deque()

# 앞쪽에 데이터 추가
deque_list.appendleft(1)
deque_list.appendleft(2)

# 뒤쪽에 데이터 추가
deque_list.append(3)
deque_list.append(4)

# 앞쪽에서 데이터 제거
print(deque_list.popleft())  # 출력: 2

# 뒤쪽에서 데이터 제거
print(deque_list.pop())  # 출력: 4

deque_list.rotate(2)
print(deque_list)  # 출력: deque([3, 4, 1, 2])

 

 

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque
from typing import Optional

class Solution:

    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        q = deque([root])

        depth = 0
        while q:
            nodes_num = len(q)
            odd_node_list = deque()
            odd_node_val_list = deque()

            for i in range(nodes_num):
                current_node = q.popleft()
                if current_node.left:
                    q.append(current_node.left)
                if current_node.right:
                    q.append(current_node.right)

                if depth % 2 == 1:
                    odd_node_list.append(current_node)
                    odd_node_val_list.appendleft(current_node.val)

            while odd_node_list:
                odd_node_list.pop().val = odd_node_val_list.pop()

            depth += 1

        return root

 

코드 설명

1. root 노드를 초기화된 deque에 추가  (처음에 그 길이는 1)
2. depth 변수를 사용하여 현재 레벨을 추적
3. BFS를 수행하면서 각 레벨의 노드를 순회 (deque의 노드들(현재 depth의 모든 nodes)를 pop하고 .left와 .right을 deque에 append)
4. 홀수 레벨의 노드를 odd_node_list와 odd_node_val_list에 저장
5. 홀수 레벨의 모든 노드 값을 역순으로 설정

시간 복잡도 분석

지금까지 bfs문제를 graph에 대해 적용해왔고, 그러할때의 시간복잡도는 O(vertex + edge)였다. 그러나 이번 문제와 같은 binary tree문제에서는 O(vertex)가 된다.

 

쉽게 생각하자면, 한 노드에 대해서 작업을 수행하면되므로 O(V)이고,

조금 detail하게 생각하지면 이진트리에서 edge의 수는 최대 vertex-1이므로 O(V+E) = O(V + V+1) = O(2V) = O(V)이다.