[알고리즘][트리] - 1. 이진 트리의 최대 깊이

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/maximum-depth-of-binary-tree/submissions/

 

이진 트리의 최대 깊이를 구하라

---

[반복 구조로 BFS 풀이]

import collections


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        q = collections.deque([root])
        depth = 0
        while q:
            depth += 1
            for _ in range(len(q)):
                current_root = q.popleft()
                if current_root.left:
                    q.append(current_root.left)
                if current_root.right:
                    q.append(current_root.right)

        return depth

 

[그래프와 트리의 차이점]

그래프	트리
순환 O	순환 X
부모 노드 여러 개여도 상관 X	부모노드 1개 이상이면 X