[LeetCode] 637. Average of Levels in Binary Tree (Python)

Problem

 

Solution

deque
defaultdict

Binary Tree 문제로 같은 레벨의 노드의 합 평균값을 구하는 문제.

값은 float 으로 반환해야된다.

left/right node를 순회하면서 defaultidct에 각 레벨별 노드값을 저장한다.

마지막에 defaultdict 에 저장된 데이터를 for문을 돌면서 합계와 평균값을 구한다.

 

아래는 다른 사람 풀이 중 하나

def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        queue = [root]
        ans = []
        while queue:
            no_nodes_in_curr_level = len(queue)

            sum_of_nodes_in_curr_level = 0

            for _ in range(no_nodes_in_curr_level):
                curr_node = queue.pop(0)
                sum_of_nodes_in_curr_level+=curr_node.val
                if curr_node.left:
                    queue.append(curr_node.left)
                if curr_node.right:
                    queue.append(curr_node.right)
            
            ans.append(sum_of_nodes_in_curr_level/no_nodes_in_curr_level)

        return ans

 

위 코드가 평균값을 레벨별로 바로바로 계산해서 저장하기 때문에 효율적일 수 있다.

하지만 pop(0) 연산은 노드 수가 많을 경우 시간 복잡도가 최악의 경우 O(n^2) 가 될 수 있으므로 deque를 사용하는 것이 낫다.

deque 는 모든 연산을 O(1) 로 처리하기 때문!

 

Code

# 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
import collections 
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        depth = collections.defaultdict(list)
        q = collections.deque()
        level = 0

        if root:
            q.append(root)
        
        while q:
            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                depth[level].append(node.val)

            level += 1

        answer = [float(sum(x)/len(x)) for x in depth.values()]
        return answer

 

Complexity

Time Complexity

각 노드 수 n 개에 비례하여 순회하므로 O(N)

 

Space Complexity

deque, defaultdict 모두 n개 만큼 공간을 사용하므로 O(N)

 

참고:

https://sahayana.tistory.com/119