BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 복습 필요

문제

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

풀이

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root == None:
                return 0

            
            l = dfs(root.left) #depth-first search
            r = dfs(root.right)

            return 1+ max(l,r)
        
        return dfs(root)

# breadth-first search, bfs => 큐 사용해서 선언
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0    
        queue = collections.deque([root])
        depth = 0

		# 큐 연산 추출 노드의 자식 노드 삽입
        while queue:
            depth += 1
            for _ in range(len(queue)):
                cur_root = queue.popleft()
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        return depth  # BFS 반복 횟수

deque -> 양방향 모두 $O(1)$ 추출