[LeetCode][Python] 111. Minimum Depth of Binary Tree

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

자 오랜만에 또 릿코드를 풀어봤습니다. 별로 풀 생각은 없었는데 알고리즘 같이 공부하자고 해서 시작을 했습니다. 일주일에 2~3문제씩 풀고 풀이하고 그럴 예정입니다

이 문제 난이도는 easy고, 이진트리의 minimum depth를 찾는 것이 목적입니다

bfs로 한 depth씩 내려가다가 리프노드 나오면 그때 depth를 반환하면 됩니다. 이 문제에서 depth는 leaf까지 오는데 거치는 노드의 수니까 2가 됩니다. 이 문제에서 노드의 value는 의미 없습니다

Example 2
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

이 문제가 좀 헷갈리는게 2번째 예제를 헷갈리게 써놨습니다. 대충 뭘 의미하는지는 알겠습니다. skewed tree 말하는 거겠죠... 근데 root = [a, b, c, ..] 이런식으로 예제가 나와 있으면 보통은 Full binary tree를 의미하는 걸로 생각하지 않나요? 이건 뭐 prefix traversal도 아니고... 뭘 나타내는지 모르겠습니다.

그냥 이 예제는 무시하시고, root 노드가 입력값으로 주어지니 로직만 집중하셔서 문제를 푸시면 되겠습니다

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        else:
            return self.dfs(root, 1)

    def dfs(self, root, step):
        # leaf
        if not root.left and not root.right:
            return step
        
        ret = 99999
        if root.left:
            ret = min(ret, self.dfs(root.left, step+1))
        if root.right:
            ret = min(ret, self.dfs(root.right, step+1))
        return ret

대충 푼 소스입니다. 위에서 풀이는 BFS로 써놨는데 왜 DFS냐고요? 문제를 검색할 때 태그에다가 dfs를 입력해서 문제를 찾았기 때문에 이 문제도 자연스럽게 dfs로 풀어버렸습니다. BFS로 다시 푸는건 귀찮으니 생략하겠습니다

이 문제는 DFS로 풀면 모든 노드 방문해야되니 비효율적입니다. 그래도 통과는 됩니다. 이 문제를 푸실 분이 있다면 BFS로 푸세요