[Leetcode 아주 상세한 문제풀이] 102. Binary Tree Level Order Traversal – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 102번 문제 Binary Tree Level Order Traversal 다.

우선 문제를 살펴보자.

 

리트코드 102번 문제 Binary Tree Level Order Traversal 링크

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal - LeetCode

 

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []
 
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 binary tree를 구성하는 root가 주어진다. 이때 'the level order traversal of its nodes' 값을 구하라는 것이다. 이것이 무슨 의미인지 문제 예시 1번을 가지고 살펴보자. 인풋으로 주어진 값으로 binary tree를 구성하면 노드 3을 가장 상단 root로 하는 binary tree 구조가 그려진다. 이때 가장 위층에는 노드 3만 존재한다. 그리고 바로 그 아래층에는 9와 20이 존재한다. 마지막으로 가장 아래 층에는 15와 7이 존재한다.

즉, 이 문제에서 말하는 'level order'의 뜻은 binary tree의 각 층을 의미힌다. 문제에서 요구하는 바는 binary tree의 가장 위에서부터 아래 방향으로 '층 별로' 노드 값을 출력하라는 것이다. 단, 같은 층에 위치한 노드값은 왼쪽 subtree에서 오른쪽 subtree로 순으로 표시해야 한다. 문제 예시 1번에서와 같이 가장 위치에는 [3], 그 바로 아래 층에는 [9, 20], 그리고 맨 아래 층에는 [15, 7]이 존재하므로 이를 묶어 리턴하면 된다. 이제 문제를 풀어보자.

 

 

문제 접근법

우리는 이 문제를 해결하기 위하여 Breadth-First Search (BFS)를 이용할 것이다.

주어진 binary tree에서 가장 상단 root에서 시작해 층 별로 탐색을 하는 것이다.

이때 queue를 이용하여 각 층의 노드들을 기억해 둘 수 있다.

BFS를 이해한다면 이 문제를 쉽게 풀 수 있으므로 BFS에 대해 좀 더 자세히 알아보자.

이 방식은 tree 혹은 graph 데이터 구조를 탐색하기 위한 알고리즘이다.

주어진 tree 혹은 graph의 임의 지점으로 시작해 주위 노드들을 탐색한 후에 다음 층 (level)으로 이동해 탐색을 계속한다.

BFS 알고리즘은 특히 최단 거리 (shortest path)를 찾는 문제에 자주 이용된다.

이 알고리즘은 특정 시작 노드를 선택해 (tree 구조의 경우 root) 그것을 방문 했다고 visited 표시 후 그것을 queue에 넣는다.

Queue가 비어있는 동안 탐색을 계속하는데 구체적인 탐색 과정은 다음과 같다.

1) Queue의 가장 앞에서 노드를 제거 (dequeue) 한다

2) 그것을 처리한다 (e.g., 출력 혹은 저장)

3-1) 아직 방문하지 않은 주변 노드 (tree 구조의 경우 subtree)를 방문한다.

3-2) 방문한 노드는 방문했다고 표시하고 (visited) 그것을 queue에 넣는다 (enqueue).

4) Queue에 아무것도 존재하지 않는 경우 종료한다. Queue에 아무것도 없다는 것은 더 이상 방문할 노드가 없다는 뜻이기 때문이다.

이제 이 문제 풀이를 코드로 한 번 살펴보자.

문제 풀이

Binary tree 구조를 표현하기 위해 class를 선언해준다. (line 1-5)

이 표현신은 파이썬에서 일반적으로 사용되니 익숙해 지도록 하자.

Binary tree의 root 값들을 입력받기 위한 함수를 정의해 준다. (line 7)

만약 입력받은 값이 없다면 빈 리스트를 리턴하고 종료한다. (line 8)

우리는 binary tree의 각 층별로 노드값을 묶으려고 하는데 노드 자체가 존재하지 않기 때문이다.

결과값을 저장하기 위한 빈 리스트를 하나 만들어 준다. (line 11)

그리고 인풋으로 입력받은 binary tree의 root를 queue에 넣어준다. (line 12)

Queue에 노드값이 존재하는 동안 탐색을 계속한다. (line 14)

먼저 queue의 길이를 계산하는데 이는 각 층에서 노드이 개수를 의미한다. (line 15)

그 후 현재 층에 위치한 노드를 저장하기 위한 변수를 만들어 준다. (line 16)

이제 각 층에 존재하는 노드 수만큼 for loop를 이용해 탐색을 진행한다. (line 18)

먼저 queue에서 가장 앞에 있는 값을 pop을 제거한다. (line 19)

그리고 그것을 미리 만들어 두었던 현재 층에 위치한 노드를 저장하기 위한 변수에 넣어준다. (line 20)

변수를 저장 후 현재 탐색하는 노드 왼쪽에 child 노드가 존재한다면 그것을 queue에 넣어준다. (line 22-23)

더불어 현재 탐색하는 노드 오른쪽에 child 노드가 존재한다면 그것을 queue에 넣어준다. (line 24-25)

이때 왼쪽 child 노드가 먼저 들어가야 함을 잊지 말자.

이런 방식으로 각 층에서 노드 탐색을 마치고 나면 각 층에 있던 노드들을 미리 만들어 두었던 result 변수에 저장한다. (line 27)

이 과정은 binary tree 전체에 대해 탐색을 마치면 최종적으로 얻어지는 result 변수를 리턴하고 종료한다. (line 29)

 

 

문제 풀이 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def levelOrder(root):
    if not root:
        return []
 
    result = []
    queue = [root]
 
    while queue:
        level_size = len(queue)
        level = []
 
        for _ in range(level_size):
            node = queue.pop(0)
            level.append(node.val)
 
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
 
        result.append(level)
 
    return result
 
# Example usage
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
 
print(levelOrder(root))  # Output: [[3], [9, 20], [15, 7]]
 

 

 

관련 문제

리트코드 98번 Validate binary search tree 문제 풀이 (링크)

리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)

리트코드 572번 Subtree of another tree 문제 풀이 (링크)

 

102. Binary Tree Level Order Traversal