leetcode - Tree - Minimum Depth of Binary Tree

 

이번 문제는 binary tree를 인자로 받아 leaf node까지의 depth 중 최소를 찾는 문제입니다.

여기서 leaf node는 왼쪽, 오른쪽 노드가 없는 것을 의미합니다.

 

저의 경우에는 재귀를 통해 leaf node를 발견할때까지 tree를 모두 순회하도록 하였습니다.

leaf node를 발견하면 leaf node의 depth를 반환하게 하여, 최소값을 구하도록 하였습니다.

 

아래는 코드입니다.

 

import sys

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        if not root.left and not root.right: return 1
        depth = sys.maxsize

        depth = min(self.findDepth(root.right, 1), self.findDepth(root.left, 1)) + 1
        return depth

    def findDepth(self, root: TreeNode, depth: int):
        if not root: return sys.maxsize
        if not root.left and not root.right: return depth
        return min(self.findDepth(root.left, depth +1), self.findDepth(root.right, depth + 1))