Сложность: 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️⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.
😎 Решение:
var hasPathSum = function (root, sum) {
if (!root) return false;
let nodeStack = [];
let sumStack = [];
nodeStack.push(root);
sumStack.push(sum - root.val);
while (nodeStack.length > 0) {
let currentNode = nodeStack.pop();
let currSum = sumStack.pop();
if (!currentNode.left && !currentNode.right && currSum === 0)
return true;
if (currentNode.right) {
nodeStack.push(currentNode.right);
sumStack.push(currSum - currentNode.right.val);
}
if (currentNode.left) {
nodeStack.push(currentNode.left);
sumStack.push(currSum - currentNode.left.val);
}
}
return false;
};Ставь 👍 и забирай 📚 Базу знаний