Сложность: 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⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.
😎 Решение:
public class Solution {
public bool HasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<int> sumStack = new Stack<int>();
nodeStack.Push(root);
sumStack.Push(sum - root.val);
while (nodeStack.Count > 0) {
TreeNode node = nodeStack.Pop();
int currSum = sumStack.Pop();
if (node.left == null && node.right == null && currSum == 0)
return true;
if (node.left != null) {
nodeStack.Push(node.left);
sumStack.Push(currSum - node.left.val);
}
if (node.right != null) {
nodeStack.Push(node.right);
sumStack.Push(currSum - node.right.val);
}
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний