2 분 소요

BFS

문제

문제 링크

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.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [3.00000,14.50000,11.00000] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Example 2:

Input: root = [3,9,20,15,7] Output: [3.00000,14.50000,11.00000]

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

스스로 고민

접근법

  • 각 층의 노드의 평균을 구해서 리스트로 반환하면된다.
    1
   / \
  2   3
 / \
4   X
  • 예를 들어서 [1,2,3,4] 이렇게 있다고 가정하면 root 층의 평균은 1
  • 그 다음 층의 (2 + 3) / 2평균은 2.5
  • 그 다음 층은 4
  • 반환은 [1, 2.5, 4] 이렇게 되며 소수점 5자리까지 허용한다.
  • 각 층의 평균을 구하는 거니까 BFS 가 제일 적합하다고 생각했다.

의사코드

  • 복습도 할겸 deque 로 구현!
  • 우선 None 값일 경우 빈 리스트를 반환해준다.
  • 결과 값을 담아줄 리스트 result를 선언
  • deque에 담아줌
  • 초기 average 변수 설정
  • floor 설정 -> 이진 트리니까 최대 갯수 2개
  • 해당 트리에서 노드가 다 계산 될 때 까지 average에 계산 값이 중첩됨
  • 해당 층에 노드 갯수로 정의해둔 floor로 나눠서 평균 값 계산
  • 다시 와일문으로 반복 되면서 average 값과 floor 초기화
  • 큐가 비어있을 때 까지 반복

    구현 코드

from collections import deque

class Solution:

    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:

        if not root:
            return []

        queue = deque([root])
        result = []

        while queue:
            average = 0
            floor = len(queue)

            for i in range(floor):
                node = queue.popleft()

                if i <= floor - 1:
                    average += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(average/floor)
        return result

시간 복잡도와 공간 복잡도

시간 복잡도: 이진 트리의 모든 노드를 한 번만 방문하므로 O(N) 다. 여기서 N은 이진 트리의 노드 수

공간 복잡도:

  1. queue 변수는 BFS(너비 우선 탐색)를 위해 사용되는 큐다. 큐는 각 레벨의 노드를 저장하는 데 사용되므로, 각 레벨에 있는 노드 수의 합이 큐에 저장된다. 이것은 최악의 경우에는 트리의 마지막 레벨의 노드 수에 해당하므로 O(N)의 공간을 사용한다.
  2. result 변수는 각 레벨의 평균 값을 저장하는 리스트다. 결과 리스트는 최대 레벨 수와 같은 길이를 가질 수 있으므로 O(H)의 공간을 사용한다. 여기서 H는 트리의 높이

회고 과정

  • 개념을 이해하니까 예전보다 문제 풀 때 확실히 수월하게 풀 수 있어서 좋았다.
  • 예전에는 어떻게 풀어야 할지 전혀 감도 안 잡힐 때가 많았는데 이럴 때는 차라리 답을 보고 접근 방법이나 문제 풀이 방법에 대한 개념을 이해하는 게 중요한 것 같다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

  • 혹시 deque를 사용하지 않고 문제를 푼 사람이 있는지 찾아보았는데 대부분 deque를 사용하고 논리도 비슷해서 다른 사람의 코드를 보는 것 보다는 어떤 상황에서 deque를 사용하면 수월한지 생각해 보는 게 낫다고 생각했다.
  • 특히 bfs, dfs 둘 다 한 번에 생각나게 연습을 해야겠다고 생각헀다.

댓글남기기

참고