[1스4코2파] #156. LeetCode pattern 637. Average of Levels in Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (156일차)
[4코1파] 2023.01.13~ (148일차)
[1스4코1파] 2023.04.12~ (59일차)
[1스4코2파] 2023.05.03 ~ (38일차)

Today :

2023.06.07 [156일차]
LeetCode Patterns
637. Average of Levels in Binary Tree

637. Average of Levels in Binary Tree

문제 설명

이진 트리가 주어질 때, 각 깊이마다 노드의 합의 평균을 구하는 것

문제 풀이 방법

stack을 이용해서 노드와 노드의 depth를 level로 칭하고, 이를 넣고
level을 넣을 dictionay 하나를 생성함

stack을 돌면서, 즉 root노드를 다 돌면서 오른쪽과 왼쪽을 탐색하면서, level dictionary에 각 level 에 대한 숫자들을 다 넣고, 마지막에는 dictionary 에 있는 레벨에 해당하는 sum을 나눠서 평균을 구하면 끝

내 코드

from collections import defaultdict

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: TreeNode) -> list[float]:
        stack = [(root, 0)]
        levels = defaultdict(list)

        while stack:
            cur_node, cur_level = stack.pop()
            levels[cur_level].append(cur_node.val)

            if cur_node.right:
                stack.append([cur_node.right, cur_level+1])
            
            if cur_node.left:
                stack.append([cur_node.left, cur_level+1])

        return [sum(level)/len(level) for level in levels.values()]

증빙

여담

오늘도 TreeNode 조지려다가 조져진 나