Сложность: easy
Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.
Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
👨💻 Алгоритм:
1⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.
2⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.
3⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.
😎 Решение:
class Solution {
func hasPathSum(_ root: TreeNode?, _ sum: Int) -> Bool {
guard let root = root else { return false }
var nodeStack = [TreeNode]()
var sumStack = [Int]()
nodeStack.append(root)
sumStack.append(sum - root.val)
while !nodeStack.isEmpty {
let node = nodeStack.removeLast()
let currSum = sumStack.removeLast()
if node.left == nil && node.right == nil && currSum == 0 {
return true
}
if let right = node.right {
nodeStack.append(right)
sumStack.append(currSum - right.val)
}
if let left = node.left {
nodeStack.append(left)
sumStack.append(currSum - left.val)
}
}
return false
}
}Ставь 👍 и забирай 📚 Базу знаний