42. Maximum Depth of Binary Tree

🎯 leetcode - 104. Maximum Depth of Binary Tree

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 42번 문제
- 이진 트리 기본 문제이다.

📌 날짜

2020.02.13

📌 시도 횟수

1 try

💡 Code

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        depth = 0

        Q = deque([root])
        while Q:
            depth += 1
            for _ in range(len(Q)):
                cur_node = Q.popleft()
                if cur_node.left:
                    Q.append(cur_node.left)
                if cur_node.right:
                    Q.append(cur_node.right)

        return depth

💡 문제 해결 방법

😸 BFS를 활용하여 풀었다.

😺 문제 해결 순서
1. 큐를 생성했다. 큐에는 현재 depth에 있는 모든 노드들이 저장된다.

2. Q에 현재 depth의 노드들을 차례대로 삽입한다.

3. 이전 depth에 Q에 삽입된 모든 요소들이 다 pop될 때까지
Q.popleft() 한 노드의 left node, right node를 다시 Q에 삽입한다.

4. 매 과정마다(while문이 한번 돌 때 마다) depth를 1 추가하여 depth를 계산한다.
모든 탐색이 끝나면 최종적으로 depth를 리턴한다.

💡 새롭게 알게 된 점

😎 트리의 각 명칭
- 깊이: 루트에서부터 현재 노드까지의 거리
- 높이: 현재 위치에서 리프까지의 거리
- 차수: 자식 노드의 개수
- 크기: 자신을 포함한 모든 자식 노드의 개수

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---