[LeetCode/Kotlin]Easy - 404. Sum of Left Leaves

[LeetCode/Kotlin]Easy - 404. Sum of Left Leaves

Sum of Left Leaves - LeetCode

문제

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

Input: root = [1]
Output: 0

Constraints:

• The number of nodes in the tree is in the range [1, 1000].

풀이

나의 풀이법

풀이 접근 과정

처음엔 TreeNode가 뭐야?? 하고 의문이었는데, 내가 위에 Example 주석을 삭제해버려서 그랬다… 얘네가 임의로 만든 클래스였구나 ^^;;

그걸 알게 되고 그냥 왼쪽 클래스를 재귀로 표현하여 바로 해결하였는데, 테스트케이스에서 오류가 났다. 알고보니 내가 문제를 제대로 읽지 않아서 생긴 오류였다. 문제에는 ‘자식이 없는 왼쪽 노드’만 더하라고 되어있었다. 그래서 자식 여부를 판단하는 함수도 만들어주었다.

최종 소스코드

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    var sum = 0
    
    fun sumOfLeftLeaves(root: TreeNode?): Int {
        if (root == null) return 0
        plusLeftLeaves(root)
        return sum
    }

    private fun plusLeftLeaves(root: TreeNode) {
        root.left?.let {
            plusLeftLeaves(root.left)
            if (haveChildren(root.left)) sum += root.left.`val`
        }
        root.right?.let {
            plusLeftLeaves(root.right)
        }
    }

    private fun haveChildren(root: TreeNode) = root.left == null && root.right == null
}

1. sumOfLeftLeaves 함수는 이 문제의 진입점입니다. 이 함수는 이진 트리의 루트 노드를 나타내는 **TreeNode**을 입력으로 받고, 왼쪽 자식 노드들의 합을 나타내는 정수를 반환합니다.
2. sum 변수는 0으로 초기화됩니다. 이 변수는 왼쪽 자식 노드들의 합을 저장하는 데 사용됩니다.
3. sumOfLeftLeaves 함수는 먼저 root 노드가 null인지 확인합니다. 만약 null이라면, 트리에 노드가 없으므로 함수는 0을 반환합니다.
4. 만약 **root**가 null이 아니라면, plusLeftLeaves 함수를 호출합니다. 이 함수는 root 노드를 시작으로 왼쪽 서브 트리를 탐색하고, 각 왼쪽 자식 노드가 왼쪽 자식이 없으면 sum 변수에 더합니다.
5. plusLeftLeaves 함수는 재귀적으로 호출되며, 왼쪽 자식 노드가 있는 경우에만 실행됩니다. **root.left**가 null이 아니라면, 왼쪽 서브 트리를 탐색하고 왼쪽 자식 노드가 있는지 확인합니다.
6. haveChildren 함수는 해당 노드가 자식 노드를 가지고 있는지 확인하는 데 사용됩니다. 노드에 자식 노드가 없으면 **true**를 반환하고, 자식 노드가 있으면 **false**를 반환합니다.
7. 따라서, plusLeftLeaves 함수는 왼쪽 자식 노드가 있는 경우 해당 노드를 시작으로 다시 plusLeftLeaves 함수를 호출하고, 왼쪽 자식 노드가 왼쪽 자식을 가지지 않는 경우 sum 변수에 더합니다. 그리고 오른쪽 자식 노드가 있는 경우에는 해당 노드를 시작으로 다시 plusLeftLeaves 함수를 호출합니다.
8. 마지막으로 sumOfLeftLeaves 함수는 sum 변수를 반환합니다.

다른 풀이법

/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

class Solution {
    fun sumOfLeftLeaves(root: TreeNode?): Int {
        if (root == null) return 0
        return sumOfLeftLeavesHelper(root, false)
    }
    
    private fun sumOfLeftLeavesHelper(node: TreeNode?, isLeft: Boolean): Int {
        if (node == null) return 0
        
        // 현재 노드가 왼쪽 잎 노드인 경우 값 반환
        if (isLeft && node.left == null && node.right == null) {
            return node.`val`
        }
        
        // 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀 호출하여 합을 계산
        val leftSum = sumOfLeftLeavesHelper(node.left, true)
        val rightSum = sumOfLeftLeavesHelper(node.right, false)
        
        return leftSum + rightSum
    }
}

1. sumOfLeftLeaves 함수는 주어진 이진 트리의 루트 노드를 받아서 왼쪽 잎 노드들의 합을 반환합니다. 루트 노드가 null이면 0을 반환합니다. 그렇지 않으면 sumOfLeftLeavesHelper 함수를 호출하여 계산을 수행합니다.
2. sumOfLeftLeavesHelper 함수는 재귀적으로 호출되며, 현재 노드와 해당 노드가 왼쪽 자식인지 여부를 인자로 받습니다. 현재 노드가 null이면 0을 반환합니다.
3. 현재 노드가 왼쪽 잎 노드인 경우(**isLeft**가 true이고 왼쪽과 오른쪽 자식이 모두 null인 경우)에는 현재 노드의 값을 반환합니다.
4. 현재 노드가 왼쪽 잎 노드가 아닌 경우, 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀 호출을 수행합니다. 왼쪽 서브트리에서는 **isLeft**를 true로 설정하여 왼쪽 자식임을 나타냅니다. 오른쪽 서브트리에서는 **isLeft**를 false로 설정합니다.
5. 마지막으로, 왼쪽 서브트리의 합과 오른쪽 서브트리의 합을 더한 값을 반환합니다.

Comment

문제를 꼼꼼히 읽자!! 그래도 크게 어렵지 않은 문제라서 IDE 없이 깔끔하게 해결하였다.