Swift) LeetCode(Easy) - Minimum Depth of Binary Tree (BFS&DFS)

leetcode.com/problems/minimum-depth-of-binary-tree/

Minimum Depth of Binary Tree - LeetCode

안녕하세요!! 짭짭이 입니다!

트리형 문제 인데요! 

일단,,,,, 문제를 풀면서 당황 스러웠던것이,,, 지금까지 트리 문제는 거의 배열 형태로 입력이 주어지고 

[][] 이차원 배열 형태로 풀었습니다.

만약에 

   3
   / \
  9  20
    /  \
   15   7

이렇게 주어지면 [0][3] / [1][9,20] / [2][15,7] 이렇게 만들어서 사용했었는데,,,

이 문제는 연결 리스트로 주어지기 때문에,,, 테스트 용 입력을 만들기 위해서 배열로 트리를 만드는 함수를 만들어야 해서

쫌 곤란한 것이 없지 않아 있었지만, 풀었습니다

 

** 문제 **

간단합니다. 그냥 루트 노드에서 모든 리프 노드가 null 인 가장 가까운 노드의 길이를 출력해주면 됩니다.

 

** 저의 풀이 **

저는 총 두가지 방법으로 풀었습니다.

처음에 풀 때는 DFS로 풀었습니다. 그냥 DFS라고 하긴 그렇고 재귀 함수 입니다.

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

방법은 아래서 부터 위로 쭉쭉 더해가는 방식 입니다.

만약 한쪽만 노드가 있을 경우 있는 쪽으로만 재귀를 돌려주고 

둘다 있다면 둘중에 작은 값을 반환 해줍니다.

 

BFS 방식은 

    func minDepth(_ root: TreeNode?) -> Int {
        guard let root = root else {return 0}
        
        var nodeInfoList : [(TreeNode?, Int)] = [(root,1)]
        
        while !nodeInfoList.isEmpty {
            
            if let nodeInfo = nodeInfoList.first {
            nodeInfoList.remove(at: 0)
            
            let node = nodeInfo.0
            let depth = nodeInfo.1
            
                if node?.left == nil && node?.right == nil {
                    return depth
                }
                else{
                    
                    if node?.left == nil && node?.right != nil {
                        nodeInfoList.append((node?.right, depth + 1))
                    }
                    else if node?.left != nil && node?.right == nil {
                        nodeInfoList.append((node?.left, depth + 1))
                    }
                    else{
                        nodeInfoList.append((node?.right, depth + 1))
                        nodeInfoList.append((node?.left, depth + 1))
                    }
                    
                }
            }
 
        }
        
        return 0
    }

이렇게 투플을 이용해서 풀었습니다.

깊이를 구하는 문제이기 때문에 처음으로 둘다 없을 경우가 가장 가까운 것이고

따라서 현재 깊이를 반환해주는 쪽으로 했습니다.

 

** 다른 사람의 풀이 ** 

sairamkotha (DFS)

final class Solution {
    var minDepth = Int.max
    
    func minDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        dfs(root, 1)
        return minDepth
    }
    
    func dfs(_ root: TreeNode?, _ level: Int) {
        if root == nil {
            return
        }
        if root!.left == nil && root!.right == nil {
            minDepth = min(level, minDepth)
        }
        dfs(root!.left, level + 1)
        dfs(root!.right, level + 1)
    }
}

 

diegostamigni (BFS)

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

 

그리고 테스트용 케이스를 만드는 Tree는 이렇게 만들었습니다.

시작할 때 배열을 주시고 index 0 부분에 아무 숫자나 넣어주시면 됩니다.

    func makeThree(_ array : [Int?], _ index : Int) -> TreeNode?{
            
        if index >= array.count {return nil}
        
        if array[index] == nil {return nil}
        
        let newNode = TreeNode(array[index])
        
        newNode.left = makeThree(array, index * 2)
        newNode.right = makeThree(array, index * 2 + 1)
        
        return newNode
    }