Table of Contents
목차
이진 트리의 최대 깊이
난이도 | ★
리트코드 104.
문제
Example 2:
Input: root = [1,null,2]
Output: 2
Example 3:
Input: root = []
Output: 0
Example 4:
Input: root = [0]
Output: 1
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
[전제]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
문제 풀기 전 알고 갈 개념
풀이과정
1) 예외처리
먼저, 트리에 아무것도 없을 때 0을 반환하는 예외처리부터 해주겠다
제일 쉬우니까 후딱 끝내버리자
Example 4:
Input: root = [0]
Output: 1
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
2) 본 문제 풀이
BFS(너비 우선 탐색)로 풀이해보겠다
- 큐로 구현
- 재귀사용 불가
[2.1 풀이 준비]
- 큐 선언
- 깊이를 기록할 변수 준비
def maxDepth(self, root: TreeNode) -> int:
...
q = collections.deque([root]) depth = 0
depth = 0
[2.2 풀이 ①]
depth=1 검출
- for문 첫번째로 돌림
[2.3 풀이 ②]
depth=2 검출
- for문 두번째로 돌림
[2.4 풀이 ②]
depth=3 검출
- for문 세번째로 돌림
전체 코드
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
q = collection.deque([root])
depth = 0
while q:
depth+=1
for _ in range(len(queue)):
cheak = q.popleft()
if cheak.left:
q.append(cheak.left)
if cheak.right:
q.append(cheak.right)
return depth