DFS: 111. Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree

 

if not root: 루트 비어 있는 경우

    return 0 : 깊이는 0

 

root 부터, 깊이는 1

 

자식이 둘다 없으면 leaf 노드 임

if not node.left and not node.right:

   return 깊이 최소 값 업데이트

 

# 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:
            return 0  # 트리가 비어있는 경우 깊이는 0

        res = [float("inf")] # 최소 깊이 찾아야 함

        def dfs(node, depth):
            if not node.left and not node.right: # 마지막 노드면
                res[0] = min(res[0], depth) # 최소 깊이 찾는 문제
                return
            
            if node.left:
                dfs(node.left, depth+1)

            if node.right:
                dfs(node.right, depth+1)

        dfs(root, 1) # root 도 깊이는 1임
        return res[0]