📕문제

LeetCode 104. Maximum Depth of Binary Tree

문제 설명

이진트리의 root가 주어졌을 때 트리의 높이를 구하는 문제다.

Example 1

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

---

📝풀이

📌DFS

오답!

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root.left and root.right:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
        elif root.left:
            return 1 + self.maxDepth(root.left)
        elif root.right:
            return 1 + self.maxDepth(root.right)
        else:
            return 1

제출한 첫번째 코드다. 아이디어는 다음과 같다.

• 해당 노드의 left, right값이 모두 존재할 경우 카운트 후 두 값 중 가장 큰 값을 반환하도록 함.
• 둘 중 하나만 존재할 경우 해당 방향으로 뻗어가며 카운트한다.
• 자식 노드가 존재하지 않는다면 해당 노드만 카운트한다.

주어진 테스트 케이스 모두 통과해 그대로 제출했지만 AttributeError가 발생했다.

AttributeError 란 속성 참조 또는 할당이 실패하면 발생하는 에러다.

노드가 존재하는 트리에서는 문제없이 작동하지만 빈 트리가 주어지면 left, right과 같은 인스턴스 변수가 없기 때문에 오류가 발생한다.
이를 해결하기 위해 root의 None검사를 먼저 진행하도록 코드를 수정했다.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

에러도 발생하지 않을뿐더러 불필요한 조건문이 줄어 코드도 간결해졌다.

📌BFS

아이디어

노드들을 레벨별로 탐색하며 가장 깊은 노드의 깊이를 구한다.

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        height = 0
        prev_queue, curr_queue = deque(), deque()
        prev_queue.append(root)
        while prev_queue:
            while prev_queue:
                node = prev_queue.popleft()
                if node.left:
                    curr_queue.append(node.left)
                if node.right:
                    curr_queue.append(node.right)
            prev_queue = curr_queue.copy()
            curr_queue.clear()
            height += 1
        return height

• prev_queue, curr_queue를 만든 후 prev_queue에 root를 삽입한다.
• prev_queue에 삽입되어 있는 노드들을 꺼냄과 동시에 자식 노드들을 curr_queue에 삽입한다.
• curr_queue에 삽입된 노드들을 prev_queue에 복사한 후 curr_queue는 초기화한다.
• 해당 단계가 한번 진행될 때마다 heigth값을 1 증가시킨다.

prev_queue에는 항상 같은 레벨의 노드들이 존재하게 된다.

코드 리팩토링

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        height = 0
        queue = deque()
        queue.append(root)
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            height += 1
        return height

• 같은 레벨의 노드의 개수를 미리 측정해 큐의 개수를 하나로 줄였다.