Path Sum

https://leetcode.com/problems/path-sumEasy

Условие

Дано бинарное дерево и целое число targetSum. Нужно определить, существует ли в дереве путь от корня до листа, сумма значений узлов на котором равна targetSum. Листом считается узел, не имеющий детей.

Примеры

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22

Output: true

Explanation: Существует путь от корня до листа, сумма узлов которого равна 22:
    5
   / \
  4   8
 /   / \
11  13  4
/ \      \
7  2      1
Input: root = [1,2,3], targetSum = 5

Output: false

Explanation: Нет пути, сумма узлов которого равна 5.
Input: root = [], targetSum = 0

Output: false

Explanation: Пустое дерево не содержит пути.

Решение

/**
 * 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
 * }
 */
fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    // Если дерево пустое, возвращаем false
    if (root == null) return false
    
    // Если это листовой узел, проверяем, равна ли его сумма значению targetSum
    if (root.left == null && root.right == null) return root.`val` == targetSum
    
    // Рекурсивно проверяем левое и правое поддеревья, уменьшая значение targetSum
    val remainingSum = targetSum - root.`val`
    return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum)
}

Временная сложность

O(n), где n — количество узлов в дереве. Мы проходим каждый узел один раз.

Пространственная сложность

O(h), где h — высота дерева, так как это максимальная глубина рекурсивного стека.