[python3] 637. Average of Levels in Binary Tree

풀이 일자: 22.09.02

난이도: [Easy]

문제 내용

주어진 트리에서 각 level별 val의 평균값의 list를 반환하는 문제

 

문제 해결 흐름

1. 트리에서 각 level별 node의 평균값을 return해야 한다.

→ 트리 순환 방법중 DFS와 BFS가 있는데 이 문제의 경우에는 둘의 방식의 차이일뿐 어떤 것을 써도 괜찮을 것 같다. 일단 구현하기 쉬운 DFS를 이용해서 풀어보자.

2. DFS로 풀어본다고 했는데 어떤 방식으로 구현하면 좋을까?

→ 어제의 문제의 풀이를 참고하여 deque를 이용하여 DFS를 구현하고 두번째 요소에 level을 표시하여 각 level별로 sum과 원소의 개수를 저장해두자.

# 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]:
        ans = list()
        ansCnt = dict()
        
        dq = deque()
        dq.append((root,0))
        
        while dq:
            node, level = dq.popleft()
            if level not in ansCnt:
                ansCnt[level] = [node.val, 1]
            else:
                ansCnt[level][0] = ansCnt[level][0] + node.val
                ansCnt[level][1] += 1
            if node.left:
                dq.append((node.left, level + 1))
            if node.right:
                dq.append((node.right, level + 1))
        
        for (total, cnt) in ansCnt.values():
            mean = round(total/cnt, 5)
            ans.append(mean)
        
        return ans

 

다른 해결 방식

1. 뭔가  같은 level에 해당하는 node의 값들의 평균을 구하는 거니까 BFS로도 풀어볼 수 있지 않을까?
< 추후 수정 >

 

 

문제 링크

https://leetcode.com/problems/average-of-levels-in-binary-tree/