릿 코드 102 Binary Tree Level Order Traversal

안녕하세요!
오늘은 릿코드 102번 문제 레벨별 순회를 Python을 이용해 풀어봅시다.

이 문제는 중간 난이도에서 트리 구조와 갑판 구조를 이해하는 데 도움이됩니다.

문제 설명

위의 트리가 입력에 들어가면 다음과 같이 반환되는 함수를 구현합니다.

위에서 레벨 1, 2, 3으로 했을 때 (3), (9,20), (15,7)이 됩니다.

Input: root = (3,9,20,null,null,15,7)
Output: ((3),(9,20),(15,7))

이번 문제는 레벨이 아래로 내려가면서 왼쪽에서 오른쪽으로 순서대로 리스트에 추가한 값을 리스트 전체에 추가해야 하기 때문에 덱을 사용하여 풀 수 있습니다.

문제 해결

데크 이용 수영장

queue 데이터 구조는 First-In-First-Out입니까? 순서에 들어간 값에 대해서, 최초에 들어간 값은 최초로 나오는 구조입니다.

Python에서는 deque라는 컬렉션 모듈에 있는 객체를 사용하여 큐의 데이터 구조를 쉽게 만들 수 있습니다.

이 데이터 구조를 이용하는 이유는 popleft() 함수를 사용하기 때문입니다.

먼저 들어오는 노드를 당겨 그 값을 노드에 저장해야하기 때문입니다.

코드에서 보자.

# 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 levelOrder(self, root: Optional(TreeNode)) -> List(List(int)):
        res = ()
        q = collections.deque()
        if root:
            q.append(root)
        
        while q:
            val = ()
            for i in range(len(q)):
                node = q.popleft()
                val.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(val)

        return res

첫째, 마지막으로 반환되는 res를 나열하고 q도 덱 구조로 만듭니다.

루트에 값이 있는 경우에만 q에 while 루프를 먼저 돌리기 전에 추가하십시오.

루트에 값이 있으면 q에 값이 들어 있으므로 루프가 시작됩니다.

val은 각각 레벨의 왼쪽에서 오른쪽으로 노드 값을 저장합니다.

어떻게 저장되는지 순서대로 이해해 봅시다.

1. q의 길이는 처음에는 1입니다.
   
   루트 노드에는 하나의 노드가 있으므로 for 문이 한 번 실행됩니다.
   
   q.popleft() 에서는, 예 1 의 그림을 보면, 루트 노드의 값이 3 이므로, 3 의 node 가 node 변수에 포함됩니다.
   
   val 리스트에 바로 node.val, 즉 3 의 값을 추가해, 좌우의 자식 노드의 유무에 따라 자식 노드를 deque 에 추가시킵니다.
   
   왼쪽 9, 오른쪽 20의 노드가 추가되고 포문이 종료됩니다.
   
   그런 다음 결과 값으로 반환되는 res 목록 변수에 val (3)이 추가됩니다.
   
   
2. 두 번째는 len(q)이 2가 됩니다.
   
   좌우의 자식 노드가 추가되어 2가 되었기 때문입니다.
   
   그리고 popleft() 가 되면(자), 9 와 20 의 왼쪽의 값인 9 가 node 변수에 격납되는 것과 동시에 q 로부터 클리어 됩니다.
   
   따라서 q 에는 20 만큼 남아, 그 후 val 에 9 의 값이 append 됩니다.
   
   9에는 자식 노드가 없으므로 q에 아무것도 추가하지 않고 종료되면 포문이 다시 실행됩니다.
   
   이 때는 popleft() 가 20 이 되고, q 에 20 이 없어지면서 val 에 20 가 추가됩니다.
   
   20 노드에는 자식 노드가 모두 있으므로 q에 좌우의 노드를 차례로 추가하면서 포문이 종료됩니다.
   
   그리고 마지막으로 val 목록에 포함된 (9, 20)이 res에 추가됩니다.
   
   
3. 세 번째로도 마찬가지로 생각할 수 있습니다.
   
   직접 시도하는 것이 좋습니다.
   
   

데크 이용 풀 성능

시간 복잡성: O(n) – 모든 노드를 반환해야 하기 때문입니다.

공간 복잡도: O(n) – 노드의 길이만 q 가 생성되어 삭제되었다고 합니다.

최악의 경우, 최하위 레벨의 노드가 가득한 Perfect binary tree인 경우 q는 n/2의 길이를 가집니다.

따라서 O(n)입니다.

---

오늘은 릿코드 102번의 문제인 Binary Tree Level Order Traversal을 Python으로 풀어 보았습니다.

Python Collections 모듈의 Deque 객체에서 사용할 수 있는 함수는 아래 링크를 참조하십시오. 감사합니다!

https://docs.python.org/en/3/library/collections.html#collections.deque

collections — Container datatypes

Source code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.,,…

docs.python.org