LeetCode Top Interview 150) Average of Levels in Binary Tree

Question

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.

Constraints:

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

# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:

---

---

보기 코드의 트리 구조의 루트 노드 root가 주어집니다.
각 레벨의 평균값을 상위 레벨부터 순서대로 리스트로 반환합니다. 평균값은 소수점 5번 째 자리까지라 표현하고 있는데 그냥 나누면 나오는 자릿수입니다. 자릿수로 신경쓸 필요는 없습니다.

제가 생각한 코드는 다음과 같습니다.

from collections import deque
# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        q = deque([(root,0)])
		answer = []
        check_depth = 0
        tmp,cnt = 0,0

        while q:
            node,now_depth = q.popleft()

            if now_depth != check_depth:
               answer.append(tmp/cnt) 
               tmp,cnt = 0,0
               check_depth+=1

            tmp += node.val
            cnt +=1

            if node.left:
                q.append((node.left,now_depth+1))
            if node.right:
                q.append((node.right,now_depth+1))
        if cnt != 0:
            answer.append(tmp/cnt)

        return answer

• q : 노드를 순회하기 위해 노드를 저장하는 큐입니다. 노드와 깊이 튜플을 원소로 가집니다. (루트노트,0)으로 초기화합니다
• answer : 특정 깊이의 평균값을 저장하는 리스트입니다.
• check_depth : 탐색해야 하는 노드의 깊이 정수값입니다.
• tmp : 탐색중인 깊이의 노드값의 합을 저장하는 변수입니다.
• cnt : 탐색중인 깊이의 노드의 갯수를 저장하는 변수입니다.
• 큐를 통한 너비우선탐색을 합니다.
  • 큐에서 노드와 노드의 깊이를 가져옵니다.
    - 깊이 탐색중인 다르다면 특정 깊이를 모두 탐색했다는 의미입니다. answer에 tmp,cnt를 이용해 평균값을 저장합니다.
  • tmp에 노드 값을 더하고 cnt를 1만큼 증가시킵니다. (깊이에서 값, 갯수 저장)
  • 서브 노드들을 큐에 추가합니다.
• 마지막 층의 평균값이 tmp,cnt에 저장만되고 answer에 추가되지 않으므로 직접 추가해줍니다.
• answer을 반환합니다.

---

너비우선 탐색을 합니다. 특정 깊이를 모두 탐색한 후 다음 노드로 넘어가는 것이 문제 조건에 어울리기 때문입니다.

모두 탐색해야 한다는 점에서 깊이 탐색으로 해도 가능하지만 코드 가독성이 떨어지거나 조건문이 더 많아질 수 있기 때문에 큐를 통해 너비우선탐색을 합니다.

문제의 조건에서 전체 탐색을 염두하고 조건을 통해 어떤 탐색을 할 지 파악했습니다. 그리고 탐색을 구현할 줄 알면 어렵지 않은 정도였고 조건을 구현하는 방식에서는 조금 생각을 하면서 풀었습니다.