leetcode.437. 路径总和 III (前缀和 + 回溯 + HashMap)

我不是女神ヾ 2022-10-10 12:54 109阅读 0赞

# [437. 路径总和 III][437. _ III] #

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 \[-1000000,1000000\] 的整数。

**示例：**

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    返回 3。和等于 8 的路径有:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3.  -3 -> 11

# 思路与代码 #

前缀和 + 回溯 + HashMap

class Solution { 
    public:
        int pathSum(TreeNode* root, int targetSum) { 
            unordered_map<int, int> worker;
            worker[0] = 1;
            int res = 0;
            dfs(root, 0, worker, res, targetSum);
            return res;
        }
    
    private:
        void dfs(TreeNode *root, int preSum, unordered_map<int, int> &worker, int &res, int target) { 
            if (!root) return;
            preSum += root->val;
            // 前缀和的本质是，把一大段数据分成 两段来看，其实中一段存在，另一段就一定存在。
            // 在前缀和公式中,当前节点前缀和就是 C , targetSum就是B , 只要知道 A 出现的次数,
            // 就知道 B 出现的次数
            // 由 A + B = C 得到 C - B = A 
            res += worker[preSum - target];
            // 加入当前前缀和
            worker[preSum]++;
            dfs(root->left, preSum, worker, res, target);
            dfs(root->right, preSum, worker, res, target);
            // 回溯
            worker[preSum]--;
        }
    };

[参考][Link 1]

[437. _ III]: https://leetcode-cn.com/problems/path-sum-iii/
[Link 1]: https://leetcode-cn.com/problems/path-sum-iii/solution/2chong-jie-fa-xiang-jie-xi-jie-wen-ti-by-txip/