Постановка задачи
Даны корень двоичного дерева и целое число targetSum,
верните true, если дерево имеет путь от корня к листьям такой, что сложение
всех значений на этом пути равно targetSum.
Лист — это узел, не имеющий детей.
Постановка задачи взята с сайта: https://leetcode.com/problems/path-sum
Пример 1:
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.
Пример 2:
Input: root = [1, 2, 3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with a sum = 5.
Пример 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
Ограничения:
- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Объяснение
Рекурсия
Для решения большинства проблем, связанных с деревьями, лучше всего использовать рекурсию или очереди/стеки.
Это одна из простых задач, которую мы будем решать с помощью рекурсии. Для решения задачи выполним следующие шаги:
-
Рекурсивно переходим к левому и правому поддереву. При каждом рекурсивном вызове уменьшайте сумму на значение текущего узла.
-
При любом рекурсивном вызове, если значение текущего узла равно оставшейся сумме, возвращаем true. Это означает, что существует путь с заданной целью.
Давайте сначала проверим алгоритм.
- if root == null
- return false
- if root->val == targetSum && root->left == null && root->right == null
- return true
- remainingTarget = targetSum - root->val
- return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget)
Давайте проверим наш алгоритм на C++, Golang и Javascript.
Решение на C++
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == NULL) {
return false;
}
if(root->val == targetSum && root->left == NULL && root->right == NULL) {
return true;
}
int remainingTarget = targetSum - root->val;
return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget);
}
};
Решение на Golang
func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}
if root.Val == targetSum && root.Left == nil && root.Right == nil {
return true
}
remainingTargetSum := targetSum - root.Val
return hasPathSum(root.Left, remainingTargetSum) || hasPathSum(root.Right, remainingTargetSum)
}
Решение для Javascript
var hasPathSum = function(root, targetSum) {
if(root == null) {
return false;
}
if(root.val == targetSum && root.left == null && root.right == null) {
return true;
}
let remainingTarget = targetSum - root.val;
return hasPathSum(root.left, remainingTarget) || hasPathSum(root.right, remainingTarget);
};
Давайте проверим наш алгоритм для примера 1.
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]
targetSum = 22
Step 1: if root == null
the root is at 5
false
Step 2: if root->val == targetSum && root->left == NULL && root->right == NULL
5 == 22
false
Step 3: remainingTarget = targetSum - root->val
= 22 - 5
= 17
Step 4: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)
root->left = 4
root->right = 8
remainingTarget = 17
Step 5: if root == null
the root is at 4
false
Step 6: if root->val == targetSum && root->left == NULL && root->right == NULL
4 == 17
false
Step 7: remainingTarget = targetSum - root->val
= 17 - 4
= 13
Step 8: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)
root->left = 11
root->right = nil
remainingTarget = 13
Step 9: if root == null
the root is at 11
false
Step 10: if root->val == targetSum && root->left == NULL && root->right == NULL
11 == 13
false
Step 11: remainingTarget = targetSum - root->val
= 13 - 11
= 2
Step 12: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)
root->left = 7
root->right = 2
remainingTarget = 2
Step 13: if root == null
the root is at 7
false
Step 14: if root->val == targetSum && root->left == NULL && root->right == NULL
7 == 2
false
Step 15: remainingTarget = targetSum - root->val
= 2 - 7
= -5
Step 16: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)
root->left = null
root->right = null
remainingTarget = -5
Step 17: if root == null
the root is null
true
We backtrack to Step 16
Step 18: if root == null
the root is null
true
We backtrack to Step 12
Step 19: if root == null
the root is at 2
false
Step 20: if root->val == targetSum && root->left == NULL && root->right == NULL
2 == 2
true
We return true here and backtrack for the rest of the tree. In the end, we have OR condition and have found the path once we return the answer as true.