[1스4코2파] #155. LeetCode pattern 111. Minimum Depth of Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (155일차)
[4코1파] 2023.01.13~ (147일차)
[1스4코1파] 2023.04.12~ (58일차)
[1스4코2파] 2023.05.03 ~ (37일차)

Today :

2023.06.07 [155일차]
LeetCode Patterns
111. Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree

문제 설명

이진 트리가 주어질 때, 최소 깊이를 구하는 문제

문제 풀이 방법

트리 내에서 루트노드가 None 이면 노드가 없으므로 0을 return 하고, 루트노드 기준으로 left, right 값을 확인해서 둘다 None 이면 루트 노드만 있으므로 min depth는 1임

그 이외에 left와 right 의 최소 깊이는 조건문을 토해서 left가 None이라면 1에 right의 깊이 만큼 더하고
right가 None이라면 1에 left의 깊이만큼 더함

위에서 A left is a node with no children.
리프 노드(단말 노드, 말단 노드, 잎 노드)는 자식노드가 없는 노드를 말하니까 최소의 left와 right 깊이의 최소를 구해서 거기에 1을 더해줌

내 코드

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:

        if not root:
            return 0

        if not root.left:
            return 1+self.minDepth(root.right)
        if not root.right:
            return 1+self.minDepth(root.left)

        return 1+min(self.minDepth(root.left), self.minDepth(root.right))

증빙

여담

dfs 깊이 우선 탐색으로 조짐
물론 조져진건 나였음