[2일차][쉬움] 111. Binary Tree의 최소 깊이

문제 링크: https://leetcode.com/problems/minimum-depth-of-binary-tree

요구 사항:

이진 트리가 주어지면 최소 깊이를 찾아야 합니다. 최소 깊이는 루트 노드와 리프 노드 사이의 경로이며 루트 노드와 가장 가까운 리프 노드 사이의 노드 수는 최소 노드 수입니다.

해결책:

깊이는 깊이를 설명하기 위해 깊이 우선 검색 알고리즘을 수정하여 계산할 수 있습니다. 한 수준 아래로 내려갈 때마다 증가하는 매개변수 깊이를 추가합니다. 자식이 없는 노드(즉, 리프 노드)를 찾은 경우 해당 지점의 깊이가 최소인지 여부를 확인합니다. 이것은 모든 리프 노드에 대해 수행됩니다(DFS는 재귀적인 철저한 알고리즘이므로).

# 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:
        minDepth = sys.maxsize
        def dfs(node: TreeNode, depth: int) -> int:
            nonlocal minDepth
            if node.left == None and node.right == None: # Leaf Node
                minDepth = min(minDepth, depth)
                return

            if node.left != None: # Go Left
                dfs(node.left, depth + 1)

            if node.right != None: # Go Right
                dfs(node.right, depth + 1)

        if root != None:
            dfs(root, 1)
            return minDepth
        return 0

추가 최적화:

우리는 깊이에만 관심이 있으므로 별도의 매개 변수를 사용하는 대신 이동 중에 계산할 수 있습니다. 탐욕스러운 재귀 알고리즘을 선택할 수 있습니다.

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        L, R = self.minDepth(root.left), self.minDepth(root.right)
        return (min(L, R) if L and R else max(L, R)) + 1

읽어 주셔서 감사합니다.