[알고리즘/python] LeetCode 637. Average of Levels in Binary Tree - BFS, deque 풀이

📑 1. 문제 이해

https://leetcode.com/problems/average-of-levels-in-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150 

Average of Levels in Binary Tree - LeetCode

 이 문제는 트리의 높이별로 원소의 평균을 구하는 문제입니다. 이때 주의해야할 점은 다음과 같습니다.

- 트리는 빈 트리일 수 없습니다.  따라서 루트는 무조건 존재합니다.

- 노드의 값은 음수가 될 수 있습니다.

- 소숫점 다섯째자리까지 정답과 비교됩니다. (answers within 10 ^ -5 of the actual answer will be accepted). 다섯째짜리까지 정확하다면 버림이나 반올림 등 소수점을 처리해주지 않아도 됩니다.

☑️ 테스트케이스

문제에서 주어진 테스트 케이스 입력값은 다음과 같습니다.

 

Example1: root = [3, 9 ,20, null, null, 15, 7]

- 마지막 레벨에 원소가 완전히 차지 않습니다.

 

Example2: root[3,9,20,15,7]

- Example1과 각 레벨의 원소 구성은 동일하지만 Example1과 달리 마지막 레벨의 원소가 왼쪽부터 오른쪽으로 차있습니다. 완전 이진 트리입니다.

배열로 트리 만들기

실제 함수의 매개변수로는 TreeNode 타입의 트리의 루트가 주어집니다. 문제를 채점하는 쪽에서 다음과 비슷한 코드로 배열을 트리로 만들고 트리의 루트를 함수의 매개변수로 제공할 것입니다.

def makeBST(arr: List[int]) -> Optional[TreeNode]:
    def create(it: Iterator[int]):
        value = next(it)
        return TreeNode(value) if value is not None else None

    if len(arr) == 0:
        return None

    it = iter(arr)
    root = TreeNode(next(it))
    nextLevel = [root]

    try:
        while nextLevel:
            level = nextLevel
            nextLevel = []
            for node in level:
                if not node:
                    continue
                node.left = create(it)
                node.right = create(it)
                nextLevel += [node.left, node.right]
    except StopIteration:
        return root

 

💡 2. 알고리즘 설계

트리를 각 레벨별로 살펴야합니다 같은 레벨에 있는 노드들을 살펴보기 위해서 넓이 우선 탐색(BFS)알고리즘을 활용할 수 있습니다. 넓이 우선 탐색은 큐를 이용한 반복구조로 구현할 수 있습니다. 큐에 동일 레벨의 노드만 기록하고, 현재 레벨의 노드를 모두 방문하였다면 큐를 다음 레벨의 노드들을 담은 큐로 교체합니다.

 

1. 빈 큐에 루트 노드를 넣습니다.

2. 반복문을 시작할때의 큐의 사이즈를 기록해두고(현재 레벨 노드의 개수), 큐에서 노드를 하나씩 꺼냅니다. 현재 노드의 값을 전체 합을 의미하는 total에 누적시킵니다. 현재 노드의 자식이 있다면 그 자식을 임시 큐에 넣습니다.

3. 모든 노드를 큐에서 꺼냈다면,  큐를 다음 레벨의 노드들을 담은 임시 큐로 교체합니다.

4.결과 배열에 계산한 평균값을 추가합니다.

4. 큐가 빌때까지, 즉 리프노드 레벨을 방문할때까지 2, 3, 4를 반복합니다.

    def averageOfLevels(self, root: TreeNode) -> List[float]:
        result = []
        queue = deque()
        queue.append(root)
        while queue:
            next_queue = deque()
            total = 0
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                total += node.val
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            result.append(total / size)
            queue = next_queue
        return result

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). while문 안에 for문이 들어있어서 O(N^2)으로 오해할 수 있지만 while문 안의 for문은 N개를 담는 것이 아니라 각 레벨의 노드들을 담습니다. 또한 while문도 N번 반복되는 것이 아니라 트리의 레벨만큼만 반복됩니다. 실제로는 모든 노드들이 한번만 queue에 들어갔다 빠지기 때문에 O(N)복잡도가 됩니다.

 

공간 복잡도: O(N). 트리의 모든 노드들이 레벨별로 저장되기 위한 큐가 필요합니다.

 ⎌ 3. 검토

문제에서 주어진 테스트 케이스들의 실행결과를 검토해보면 다음과 같습니다.

 

Example1: root = [3, 9 ,20, null, null, 15, 7]

- 9의 경우 자식이 없습니다. 왼쪽, 오른쪽 노드가 빈 겨우 트리에 추가되지 않습니다. 큐에 None이 삽입되지 않기 때문에 큐에서 꺼낸 값에 대해서 node.val로 참조하여도 AttributeError('NoneType')이 발생하지 않습니다.

 

Example2: root[3,9,20,15,7]

- 값이 7인 TreeNode의 left, right가 None입니다. 큐에 None이 삽입되지 않기 때문에 큐에서 꺼낸 값에 대해서 node.val로 참조하여도 AttributeError('NoneType')이 발생하지 않습니다.

---

🤔 다른 사람의 풀이

모든 노드를 한번씩 방문해야하고 넓이 우선 탐색을 해야합니다. 또한 위의 풀이에서 불필요하거나 중복된 연산이 존재하지 않기 때문에 유의미하게 더 빠른 풀이는 존재하지 않는다고 생각합니다.

---

✅ 정리

◎ 넓이 우선 탐색시에 레벨 별로 나눠서 살펴보기 위해서는 1) queue를 레벨 별로 교체하면서 사용하거나 2) 큐에 삽입할때 level을 함께 넣어줄 수 있습니다.