我无法为以下问题提出迭代解决方案（即不递归或使用调用堆栈）。因此，请向这里的社区寻求您的帮助。 :)
问题 给定二叉树的根和整数 targetSum，返回路径上的值之和等于 targetSum 的路径数。该路径不需要从根或叶开始或结束，但必须向下（即仅从父节点到子节点）。
例如： 根 = [10,5,-3,3,2,null,11,3,-2,null,1]，总和 = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 说明：显示总和为 8 的路径。
其他测试用例：
失败的测试用例图片：
-2
\
-3
以上所有测试均通过，但最后一个测试失败。我的代码返回 0，但预期输出为 1，因为有一个节点本身的值为 -3，并且等于 targetSum，因此等于 targetSum 的节点数应等于 1。
我很难修复我的解决方案，使其适用于最后一个测试用例，同时确保其他测试用例都不会失败。
我的迭代解决方案：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {number}
*/
var pathSum = function(root, targetSum) {
let count = 0, cache = new Map();
let stack = [[root, 0]];
while (stack.length) {
let [node, currSum] = stack.pop();
if (node) {
currSum += node.val;
if (currSum === targetSum) {
count++;
}
count += cache.get(currSum-targetSum) || 0;
cache.set(currSum, (cache.get(currSum) || 0) + 1);
stack.push([node.right, currSum]);
stack.push([node.left, currSum]);
if (!node.left) {
cache.set(currSum, cache.get(currSum) - 1);
}
}
}
return count;
};
我已经有一个使用递归进行遍历的工作解决方案，但这个问题仅适用于基于迭代遍历的解决方案。我觉得当我们使用堆栈迭代遍历二叉树时，我错过了有关回溯如何工作的一些内容。如果您发现任何错误，请告诉我！
问题是您没有一个好的方法来知道何时从缓存中“删除”计数。在您执行删除计数的地方，它在添加计数后立即跟随，这是不正确的。其间发生的 push 指令并没有真正改变这一事实。如果在这种情况下（
!node.left我建议添加另一个结构来跟踪
在哪个树深度将计数添加到缓存中。然后，当您弹出具有一定深度的节点时，您知道应该删除任何大于深度的缓存。 这是您根据该想法改编的代码，我没有对其进行不必要的更改。评论指出了我所做的更改：
var pathSum = function(root, targetSum) {
let count = 0, cache = new Map();
const depthLog = []; // Keep track of cache actions per depth (index in array)
let stack = [[root, 0, 0]]; // Add the depth of the node as 3rd member
while (stack.length) {
let [node, currSum, depth] = stack.pop(); // Expect the 3rd member
if (node) {
// Remove cache that is no longer relevant
while (depthLog.length > depth) {
for (const sum of depthLog.pop()) {
cache.set(sum, cache.get(sum) - 1);
}
}
//
currSum += node.val;
if (currSum === targetSum) {
count++;
}
count += cache.get(currSum-targetSum) || 0;
cache.set(currSum, (cache.get(currSum) || 0) + 1);
(depthLog[depth] ??= []).push(currSum); // Also log the act of caching this sum
stack.push([node.right, currSum, depth+1]); // Add depth
stack.push([node.left, currSum, depth+1]); // ...
// Removed the `if` block at this place
}
}
return count;
};
此扩展不会影响时间复杂度：缓存删除的复杂度与添加计数的复杂度相同（只能删除之前添加的内容）。