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