[코테] 리트코드 트리 104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree

문제 링크

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

문제 설명

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

제한 사항

• The number of nodes in the tree is in the range [0, 10^4].
• -100 <= Node.val <= 100

입출력 예 #1

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

입출력 예 #2

1. Input : root = [1,null,2]
2. Output : 2

문제 풀이

bfs 기법을 이용해서 해당 노드의 자식 노드들을 queue에 넣고, queue에 남아있는 항목이 있으면 depth에 1씩 더하면서 반복한다.

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.leff)
                if cur_root.right:
                    queue.append(cur_root.right)

        # BFS 반복 횟수 == 깊이
        return depth