Постановка задачи
Учитывая корень бинарного дерева и целое число targetSum, вернуть все пути от корня к листу, где сумма узлов значения в пути равны targetSum. Каждый путь должен быть возвращен в виде списка значений узлов, а не ссылок на узлы.
Путь от корня к листу — это путь, начинающийся от корня и заканчивающийся любым конечным узлом. Листок — это узел без дочерних элементов.
Постановка задачи взята с: https://leetcode.com/problems/path-sum-ii
Пример 1:
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Пример 2:
Input: root = [1, 2, 3], targetSum = 5
Output: []
Пример 3:
Input: root = [1, 2], targetSum = 0
Output: []
Ограничения:
- The number of nodes in the tree is in the range [0, 5000]
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Объяснение
Проблема похожа на нашу предыдущую запись в блоге Сумма путей. Здесь мы будем использовать тот же алгоритм, но также будем хранить значения узлов дерева в массиве.
Сначала проверим алгоритм.
- set 2D array vector<vector<int>> result
1D array vector<int> current
- getPathSum(root, result, current, targetSum)
- return result
// getPathSum function
- if root == NULL
- return
- if root->val == targetSum && root->left == NULL && root->right == NULL
- current.push_back(root->val)
- result.push_back(current)
- return
- set remainingTargetSum = targetSum - root->val
- current.push_back(root->val)
- getPathSum(root->left, result, current, remainingTargetSum)
- getPathSum(root->right, result, current, remainingTargetSum)
- return
Давайте проверим наш алгоритм на C++, Golang и Javascript.
С++ решение
class Solution {
public:
void getPathSum(TreeNode* root, vector<vector<int>> &result, vector<int> current, int targetSum) {
if(root == NULL) {
return;
}
if(root->val == targetSum && root->left == NULL && root->right == NULL) {
current.push_back(root->val);
result.push_back(current);
return;
}
int remainingTargetSum = targetSum - root->val;
current.push_back(root->val);
getPathSum(root->left, result, current, remainingTargetSum);
getPathSum(root->right, result, current, remainingTargetSum);
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
vector<int> current;
getPathSum(root, result, current, targetSum);
return result;
}
};
Голанг решение
func getPathSum(root *TreeNode, result *[][]int, current []int, targetSum int) {
if root == nil {
return
}
if root.Val == targetSum && root.Left == nil && root.Right == nil {
current = append(current, root.Val)
*result = append(*result, append([]int(nil),current...))
return
}
remainingTargetSum := targetSum - root.Val
current = append(current, root.Val)
getPathSum(root.Left, result, current, remainingTargetSum)
getPathSum(root.Right, result, current, remainingTargetSum)
return
}
func pathSum(root *TreeNode, targetSum int) [][]int {
result := [][]int{}
current := []int{}
getPathSum(root, &result, current, targetSum)
return result
}
Javascript-решение
var pathSum = function(root, targetSum) {
let result = [];
var getPathSum = function(root, current, targetSum) {
if(root === null) {
return;
}
if(root.val === targetSum && root.left === null && root.right === null) {
result.push([...current, root.val]);
return;
}
let remainingTargetSum = targetSum - root.val;
getPathSum(root.left, [...current, root.val], remainingTargetSum);
getPathSum(root.right, [...current, root.val], remainingTargetSum);
return;
}
getPathSum(root, [], targetSum);
return result;
};
Давайте протестируем наш алгоритм для примера 1.
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
targetSum = 22
Step 1: initialize vector<vector<int>> result;
vector<int> current;
Step 2: getPathSum(root, result, current, targetSum)
getPathSum(root, [[]], [], 22)
the root is at 5
// getPathSum
Step 3: if root == NULL
false
if root->val == targetSum && root->left == NULL && root->right == NULL
5 == 22
false
remainingTargetSum = targetSum - root->val
= 22 - 5
= 17
current.push_back(root->val)
current = [5]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(4, [[]], [5], 17)
Step 4: if root == NULL
the root is at 4
false
if root->val == targetSum && root->left == NULL && root->right == NULL
4 == 17
false
remainingTargetSum = targetSum - root->val
= 17 - 4
= 13
current.push_back(root->val)
current = [5, 4]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(11, [[]], [5, 4], 13)
Step 5: if root == NULL
the root is at 11
false
if root->val == targetSum && root->left == NULL && root->right == NULL
11 == 13
false
remainingTargetSum = targetSum - root->val
= 13 - 11
= 2
current.push_back(root->val)
current = [5, 4, 11]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(7, [[]], [5, 4, 11], 2)
Step 6: if root == NULL
the root is at 7
false
if root->val == targetSum && root->left == NULL && root->right == NULL
7 == 2
false
remainingTargetSum = targetSum - root->val
= 2 - 7
= -5
current.push_back(root->val)
current = [5, 4, 11, 7]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(NULL, [[]], [5, 4, 11, 7], -5)
Step 7: if root == NULL
the root is NULL
true
We backtrack to step 6 and continue
Step 8: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(2, [[]], [5, 4, 11], 2)
Step 9: if root == NULL
the root is at 2
false
if root->val == targetSum && root->left == NULL && root->right == NULL
2 == 2 && root->left == NULL && root->right == NULL
true
current.push_back(root->val)
current = [5, 4, 11, 2]
result.push_back(current)
result = [[5, 4, 11, 2]]
return
We backtrack to step 4 and continue
Step 10: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(NULL, [[5, 4, 11, 2]], [5, 4], 13)
Step 11: if root == NULL
the root is NULL
true
We backtrack to step 3 and continue
Step 12: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(8, [[5, 4, 11, 2]], [5], 17)
Step 13: if root == NULL
the root is at 8
false
if root->val == targetSum && root->left == NULL && root->right == NULL
8 == 17
false
remainingTargetSum = targetSum - root->val
= 17 - 8
= 9
current.push_back(root->val)
current = [5, 8]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(13, [[5, 4, 11, 2]], [5, 8], 9)
Step 14: if root == NULL
the root is at 13
false
if root->val == targetSum && root->left == NULL && root->right == NULL
13 == 9
false
remainingTargetSum = targetSum - root->val
= 9 - 13
= -4
current.push_back(root->val)
current = [5, 8, 13]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)
Step 15: if root == NULL
the root is NULL
true
We backtrack to step 14 and continue
Step 16: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)
Step 17: if root == NULL
the root is NULL
true
We backtrack to step 13 and continue
Step 18: getPathSum(root->right, result, current, remainingTargetSum)
getPathSum(4, [[5, 4, 11, 2]], [5, 8], 9)
Step 19: if root == NULL
the root is at 4
false
if root->val == targetSum && root->left == NULL && root->right == NULL
4 == 9
false
remainingTargetSum = targetSum - root->val
= 9 - 4
= 5
current.push_back(root->val)
current = [5, 8, 4]
getPathSum(root->left, result, current, remainingTargetSum)
getPathSum(5, [[5, 4, 11, 2]], [5, 8, 4], 5)
Step 20: if root == NULL
the root is at 5
false
if root->val == targetSum && root->left == NULL && root->right == NULL
5 == 5
true
current.push_back(root->val)
current = [5, 8, 4, 5]
result.push_back(current)
result = [[5, 4, 11, 2], [5, 8, 4, 5]]
return
We backtrack to step 19 and continue
Once the last rightmost lead node is processed
we return the result
The answer is [[5, 4, 11, 2], [5, 8, 4, 5]].
Первоначально опубликовано на https://alkeshghorpade.me.