[Leetcode/파이썬] 637. Average of Levels in Binary Tree

Average of Levels in Binary Tree

---

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

 

# 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]:
        dummy = root
        idx = 0
        lst = [[] for _ in range(10**4 + 1)]
        res = []

        self.average_tree(dummy, 0, lst)

        while lst[idx] :
            length = len(lst[idx])
            res.append(sum(lst[idx]) / length)
            idx += 1
        
        return res
        
    def average_tree(self, tree: Optional[TreeNode], idx: int, lst: List) :
        if tree.left is None and tree.right is None :
            lst[idx].append(tree.val)
            return 

        if tree.left :
            self.average_tree(tree.left, idx+1, lst)
        if tree.right :
            self.average_tree(tree.right, idx+1, lst)

        lst[idx].append(tree.val)
        return

첫 번째 방법은 DFS 방식이다. lst를 하나 만든다. 경계값이 1만이라서 리스트를 1만 1개 만큼 만들었다. 어차피 사용할 것들은 앞에서 부터 사용될 테니 메모리 누수가 조금 있더라도 이렇게 사용하는 것이 더 낫지 않을까 생각해서 이렇게 만들었다. 그리고 정답을 담을 res 리스트도 하나 만들었다. 

평균 계산을 하러 간다. 이때 DFS라서 리프노드 부터 계산을 해야 한다. 방문은 아마 Post Order? 맞나? 이렇게 될 거 같다. Pre Order 인가? 아마 Post Order 라 하자. 이따 스터디 때 물어봐야지. (일단 Post Order가 맞는거 같은데 정확하지 않아서 이따 스터디 하고 나면 수정)

양쪽에 자식 노드가 없으면 그 노드 값을 일단 $lst[이 노드의 레벨]$ 에 저장하고 반환. 

만약 왼쪽이나 오른쪽, 혹은 양쪽이 존재하면 계속해서 방문해서 내려간다. 그리고 모든 방문이 끝났으면 마지막으로 남아 있는 노드를 하나 추가 하고 종료 한다. => 이것도 디버깅 과정에서 하다가 알게 된건데 정확하게 어떻게 추가가 되는지는 알아봐야 겠다. 그림은 아직 안 그려봤다. 

이렇게 해서 모든 노드를 방문한 후 평균 값을 구한 값을 res에 레벨 별로 추가한다. idx + 1 씩 해가면서 만약 빈 lst가 발견되면 종료 하는걸로.

아직 풀리지 않은 것

1. average_tree 함수가 post order 인지 pre order 인지.
2. 마지막 lst[idx].append(tree.val)을 디버깅 과정에서 추가하게 되었는데 어째서 추가해야 통과가 되었는지에 대해서.

# 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]:
        dummy = root
        q = deque()
        q.append(dummy)
        averages = []

        while q :
            lv_sum, length = 0, len(q)
            for _ in range(length) :
                node = q.popleft()
                lv_sum += node.val
                if node.left :
                    q.append(node.left)
                if node.right :
                    q.append(node.right)

            averages.append(lv_sum / length)

        return averages

두 번째 방법은 BFS 이다. 아마 문제에서 요구한 풀이는 이쪽에 더 가깝지 않나 생각한다. 그 이유는 DFS의 경우, 깊이 우선 탐색이다보니 같은 레벨에서의 계산 보다는 리프 노드 중 가장 왼쪽에 있는 아이부터 방문을 하게 된다. BFS는 같은 레벨에 있는 노드부터 먼저 방문하게 되므로 이번 문제에서는 BFS가 더 적절한 풀이라고 생각한다. => 근데 전에 풀어놓고 생각을 못함...

초기 세팅은 더미선언, 데크, 데크에 더미 집어넣기, 정답처리할 averages 리스트 선언 

BFS 실행 (이번 BFS는 전에 해왔던 BFS 방식과는 조금 거리가 있는 문제 풀이였다.)

1. BFS 초기값 세팅 : 같은 레벨에서 존재하는 노드 값의 합(초기값은 0), 노드 갯수 
2. 루트 노드 바로 방문하면 계산해서 averages 에 추가
3. for문 내에서 같은 레벨에 존재하는 모든 노드의 합을 구하고, averages 리스트에 추가할 때 평균 계산을 하기 때문에
   for문이 레벨을 가르는 경계선 같은 역할이라 보면 된다.
4. averages에 평균을 계산한 후 추가.
5. 다음 레벨을 진행할 때는 자연스레 같은 레벨의 노드의 합은 0, 같은 레벨의 노드 갯수는 len(q)로 초기화 된다. 

이렇게 보니까 조금만 생각하면 BFS로 푸는게 더 나은 방향이겠다는 생각이 들었다. 

이 문제는 처음 푸는 문제는 아닌데 이번에는 DFS 방식으로 문제를 해결해 보았다. 두 번째 풀이는 BFS 방식으로 이 방식은 아마 다른 분의 코드를 참고해서 예전에 풀었던 방식이었던 것 같다.

이 문제를 보고 나서 DFS를 조금 더 공부할 수 있어서 좋았고, BFS 뿐만 아니라 DFS로도 풀이 할 수 있어서 좋았다.