[알고리즘] Leetcode-maximum-depth-of-binary-tree 파이썬 문제 풀이

문제 링크

문제

2진 트리의 최대 깊이를 반환하는 문제이다.

입출력 예시

조건

최대 깊이가 10의 4승이다. n^2은 약간 간당간당하니 더 낮은 알고리즘으로 푸는게 안전하다.

풀이 - BFS

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        max_depth = 0
        if root is None:
            return 0
        q = deque()
        q.append((root, 1))
        while q:
            cur_node, cur_depth = q.popleft()
            max_depth = max(max_depth, cur_depth)
            
            if cur_node.left:
                q.append((cur_node.left, cur_depth + 1))
            if cur_node.right:
                q.append((cur_node.right, cur_depth + 1))
                
        return max_depth

BFS로 모든 노드를 탐색하고 Queue에 넣어줄 때 현재 노드의 깊이를 함께 넣어서 구했다.

풀이 - DFS

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        left = self.maxDepth(root=root.left)
        right = self.maxDepth(root=root.right)
        return max(left, right) + 1

이번 풀이는 재귀를 활용한 DFS 방식을 사용했다. 깊이 들어갈 수 있을 때까지 들어가서 깊이를 반환해주는 방법을 사용했다.