二叉树目标路径和迭代解法问题求助（含失败测试用例）

问题背景 #

需要实现二叉树目标路径和的迭代解法（禁止递归或调用栈）：给定二叉树根节点与整数targetSum，统计向下路径（仅从父到子）的和等于targetSum的路径数量，路径无需从根或叶子开始。

现有迭代代码在测试用例root=[-2,null,-3]、targetSum=-3时返回0，预期结果为1（节点-3自身符合条件），需定位错误并修复。

错误分析 #

原代码的核心问题在于前缀和缓存（cache）的回溯逻辑完全错误：

• 仅在节点无左子节点时才减少cache计数，不符合二叉树遍历的回溯规则——遍历完节点的所有子节点后，必须将当前节点的前缀和从cache中移除，避免影响其他分支的计算。
• 栈元素未标记访问状态，导致首次处理节点时直接修改cache，但后续子节点处理完成后无法正确回溯。

修复方案 #

采用标记法处理栈元素，每个栈元素存储[节点, 当前前缀和, 是否已访问]：

1. 首次弹出未访问节点时，计算当前前缀和、统计符合条件的路径数，更新cache后，将节点标记为已访问重新压入栈，再压入右、左子节点（未访问）。
2. 弹出已访问节点时，执行回溯操作：从cache中减去当前前缀和的计数，确保其他分支不受当前子树的前缀和影响。
3. 初始化cache时加入[0, 1]，用于处理路径从当前节点自身开始的情况（比如单独节点值等于targetSum的场景）。

修复后的代码 #

/**
 * 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;
    // 初始化前缀和缓存：前缀和0出现1次，处理路径从当前节点自身开始的情况
    const cache = new Map([[0, 1]]);
    // 栈元素格式：[节点, 父节点前缀和, 是否已访问]
    const stack = root ? [[root, 0, false]] : [];

    while (stack.length) {
        const [node, prevSum, isVisited] = stack.pop();

        if (!isVisited) {
            // 首次处理节点：计算当前前缀和，统计符合条件的路径数
            const currSum = prevSum + node.val;
            // 查找是否存在前缀和等于currSum - targetSum，存在则累加计数
            count += cache.get(currSum - targetSum) || 0;
            // 更新缓存：当前前缀和计数+1
            cache.set(currSum, (cache.get(currSum) || 0) + 1);

            // 先压入标记为已访问的当前节点（后续处理回溯）
            stack.push([node, currSum, true]);
            // 压入右子节点（未访问）
            if (node.right) stack.push([node.right, currSum, false]);
            // 压入左子节点（未访问）
            if (node.left) stack.push([node.left, currSum, false]);
        } else {
            // 回溯操作：当前节点的子树已遍历完成，移除当前前缀和的计数
            const currSum = prevSum;
            cache.set(currSum, cache.get(currSum) - 1);
            // 计数为0时删除键，避免后续干扰
            if (cache.get(currSum) === 0) {
                cache.delete(currSum);
            }
        }
    }

    return count;
};

验证测试用例 #

针对root=[-2,null,-3]、targetSum=-3的场景：

1. 处理根节点-2：前缀和为-2，currSum - targetSum = -2 - (-3) = 1，缓存中无1，count保持0；缓存新增-2:1。
2. 压入已访问的-2，再压入右子节点-3（未访问）。
3. 处理-3：前缀和为-2 + (-3) = -5，currSum - targetSum = -5 - (-3) = -2，缓存中有-2:1，count加1（变为1）；缓存新增-5:1。
4. 压入已访问的-3，无左右子节点，弹出已访问的-3时，移除缓存中的-5计数。
5. 弹出已访问的-2时，移除缓存中的-2计数。
   最终返回count=1，符合预期。

内容的提问来源于stack exchange，提问作者Uthman