[Kotlin] LeetCode 1302 : Deepest Leaves Sum

Deepest Leaves Sum - LeetCode

간단하게 이진 트리를 탐색하는 문제입니다.
가장 깊은 위치에 존재하는 리프노드들의 value 총합을 구해야 합니다. 이를위해 아래와 같은 2가지 과정이 필요하다는 것을 쉽게 파악할 수 있습니다.

1. 가장 깊은 노드가 위치한 깊이가 몇인지?? 이를 maxDepth라고 해봅시다.
2. maxDepth를 알았으니, 해당 깊이에 존재한 노드를 찾아 value의 총합을 구해줍니다.

따라서 DFS 두번으로 해결할 수 있고, 깊이를 구하는 깊이 탐색과, 특정 깊이에 들어있는 노드의 총합을 구하는 깊이 탐색을 수행해줍시다.

import kotlin.math.max

class Solution {
    fun deepestLeavesSum(root: TreeNode?): Int {
        val maxi : Int = getMaxDepth(root)
        return dfs(root, maxi, 1)
    }
    
    fun dfs(node : TreeNode?, depth : Int, curr : Int) : Int {
        if(node == null) return 0
        if (isEqual(depth, curr)) {
            return getValue(node)
        }
        return dfs(node!!.left, depth, curr+1) + dfs(node!!.right, depth, curr+1)
    }
    
    fun getMaxDepth(node : TreeNode?) : Int {   
        if(node == null) return 0
        return max(
            getMaxDepth(node!!.left) + 1, 
            getMaxDepth(node!!.right) + 1
        )
    }
    
    fun getValue(node : TreeNode) : Int = node.`val`
    
    fun isEqual(a : Int, b : Int) : Boolean = (a == b)
}