[Swift 알고리즘] LeetCode 1302 - Deepest Leaves Sum

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

Deepest Leaves Sum - LeetCode

 

풀이

1302 문제의 주의점은 leaf 노드가 아니라 최대 깊이의 노드의 합이라는 것입니다.

 

예시 1을 보면 node 5는 자식이 없는 leaf 노드지만 최대 depth가 아니기 때문에 결과 합에 포함되지 않습니다.

따라서 재귀를 이용한 dfs를 통해 depth를 체크하면서

최대 depth일 때 val을 더해주면 됩니다.

 

전체 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    
    var sum: Int = 0
    var maxDepth: Int = 0
    
    func deepestLeavesSum(_ root: TreeNode?) -> Int {
        dfs(root, depth: 0)
        return sum
    }
    
    func dfs(_ node: TreeNode?, depth: Int) {
        guard let node = node else { return }
        
        if maxDepth == depth {
            sum += node.val
        } else if maxDepth < depth {
            maxDepth = depth
            sum = node.val
        }
        
        dfs(node.left, depth: depth + 1)
        dfs(node.right, depth: depth + 1)
    }
}
// Runtime: 310 ms, faster than 84.38% of Swift online submissions for Deepest Leaves Sum.
// Memory Usage: 15.1 MB, less than 54.17% of Swift online submissions for Deepest Leaves Sum.

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.