LeetCode 111(Minimum Depth of Binary Tree, Python)

1. 문제 링크

• Minimum Depth of Binary Tree - LeetCode

Minimum Depth of Binary Tree - LeetCode

2. 문제 설명

• 이진 트리 구조가 주어졌을 때 Minimum Depth를 구하기
• 예시) 아래의 이진 트리의 경우 Minimum Depth는 2(3-9)

   3

  /\

9 20

    /\

 15  7

3. 처음 풀이

• 이제 이진 트리 구조에서 재귀 함수 사용하는 것에 약간 익숙해졌음. 
• 어떤 노드에서 바닥까지 내려가는 Minimum Depth는
  • 해당 노드에서 왼쪽, 오른쪽 서브 트리가 모두 있을 때는 양쪽의 Minimum Depth중 min 값에 +1을 해주면 되고
  • 해당 노드에서 한쪽만 서브트리가 있다면 거기에 +1을 해주면 된다. 그런데 없는 경우 0을 반환하도록 한다면 양쪽 값 중 max 값에 +1을 하면 된다. 

# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if not root: #None -> depth = 0
            return 0
        left = self.minDepth(root.left) #minimum depth of left sub tree
        right = self.minDepth(root.right) #minimum depth of right sub tree
        if not left or not right: #left==None or right==None -> None이 아닌 쪽 +1, None 이면 0이니까 양쪽 중 max 값 +1
            return max(left, right)+1
        else: #양쪽이 모두 있으면 양쪽 중 빠른 길로 간다. min 값 +1
            return min(left, right)+1

4. 다른 풀이

• 이 문제는 다른 사람들 풀이도 대부분 비슷한 논리

5. 배운 점

• 딱히 새로운 내용은 없다. 이진 트리에서는 역시 재귀를 자주 사용한다. 
• 재귀 함수를 이용할 때는 가장 일반적으로 반복되는 상황을 먼저 생각하고, 재귀가 마무리 될 조건에 유의하여 코드를 작성한다.