[Leetcode - Swift] 111. Minimum Depth of Binary Tree

문제

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

Minimum Depth of Binary Tree - LeetCode

 

풀이

 1. 재귀

 2 .BFS

 

 최소 깊이를 찾는다는 것은 자식 노드가 아무 것도 없는 노드를 빨리 발견하는 것이다.

 그래서 BFS로 순회하면서 자식 노드가 없는 노드를 발견하면 그때의 깊이를 반환하려는 풀이 방법을 생각했다.

 하지만, BFS를 Queue로 구현하면서 깊이를 어떻게 계산해주어야 할지 생각이 안났다.

 

 그래서, 104번 문제와 비슷하게 재귀를 이용하여 풀었다.

 본 함수를 재귀적으로 호출하면서 왼쪽 값, 오른쪽 값의 최소값을 반환하도록 했다.

 최소 깊이를 찾는 즉시 순회를 종료하는 BFS와 달리, 모든 노드를 순회하기 때문에 시간복잡도가 조금 더 걸린다.

 하지만 worst case는 O(n)으로 같다.

 

코드

// 1. 재귀

class Solution {
    func minDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        
        let left = minDepth(root.left)
        let right = minDepth(root.right)
        
        if left == 0 {
            return right + 1
        } else if right == 0 {
            return left + 1
        } else {
            return min(left, right) + 1
        }
    }
}

 

// 2. BFS

class Solution {
    func minDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        
        var queue: [TreeNode?] = [root]
        var depth = 1
        
        while !queue.isEmpty {
            depth += 1
            for _ in 0..<queue.count {
                let current = queue.removeFirst()
                
                if let left = current?.left {
                    queue.append(left)
                }
                if let right = current?.right {
                    queue.append(right)
                }
                
                if current?.left == nil && current?.right == nil {
                    return depth
                }
            }
        }
        
        return depth
    }
}