[ 알고리즘 ] LeetCode 637. Average of Levels in Binary Tree

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 637. Average of Levels in Binary Tree를 풀고 작성한 글입니다.

문제

요구사항

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.

제약사항

• The number of nodes in the tree is in the range [1, 10^4] .
• -2^31 <= Node.val <= 2^31 - 1

풀이

접근법

총 두 가지 풀이가 존재한다.

1. 전위 탐색범(Preorder Traverse)을 활용하여 재귀 함수(Recursion Function)를 호출하는 방법
2. 덱큐(Dequeue)를 활용하여 너비 우선 탐색(Breadth First Search)을 수행하는 방법

첫 번째 풀이

먼저 아래와 같이 재귀 함수를 호출해서 문제를 해결할 수 있다.

def solution(root: "TreeNode") -> list[float]:
    def traverse(depth: int, node: TreeNode) -> None:
        nonlocal tree
        if node:
            if depth in tree:
                tree[depth].append(node.val)
            else:
                tree[depth] = [node.val]
            
            traverse(depth=depth+1, node=node.left)
            traverse(depth=depth+1, node=node.right)

    
    tree: dict[int, int] = {}
    traverse(depth=0, node=root)
    
    answer: list[float] = [ 0 for _ in range(len(tree)) ]
    for index, value in tree.items():
        answer[index] = sum(value) / len(value)
    
    return answer

두 번째 풀이

다음으로 collections 내장 모듈에 있는 deque 객체를 활용하여 BFS로 문제를 해결할 수 있다.

def solution(root: "TreeNode") -> list[float]:
    from collections import deque
    
    
    queue: deque = deque([root])
    answer: list[float] = []
    while queue:
        same_level_count = same_level_length = len(queue)
        same_level_sum: int = 0
        
        while same_level_count > 0:
            node: TreeNode = queue.popleft()            
            if node.left:
                queue.append(node.left)
            
            if node.right:
                queue.append(node.right)
                
            same_level_sum += node.val
            same_level_count -= 1
        
        answer.append(same_level_sum / same_level_length)
        
    return answer  

이때 유의할 점은 중첩된 내부 while 문에서 처음에 popleft() 메서드 호출로 인해 queue 객체가 비었을 때 그 외부 while 문의 조건에 위배되어 즉시 반복문이 중단될 줄 알았는데 우선적으로 실행 중이던 반복문은 한 번 다 수행한 뒤에 종료가 된다는 점이다.

그래서 popleft() 메서드 호출로 인해 객체가 비었어도 그 다음 라인에 node 객체에 좌측 혹은 우측에 자식 노드가 존재한다면 다시 객체에 append() 메서드 호출을 통해 추가가 되기 때문에 반복문이 중단되지 않고 원하는 대로 작동한다.

일례로 아래 코드의 경우 "Converted" 까지만 출력하고 프로그램이 종료되는 것이 아닌 "After" 까지 출력한 뒤에 프로그램이 종료된다.

flag: bool = True
while flag:
    print("Before")
    
    if flag:
        print("Converted")
        flag = False
    
    print("After")

시간 복잡도

첫 번째 풀이와 두 번째 풀이 모두 주어진 트리의 노드 개수만큼만 반복문을 수행하면 되기 때문에 시간 복잡도는 O(N)이다.