Leetcode 437.路径总和 III

题目描述：

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

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

示例 1：

1
2
3

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

1
2

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

链接：

https://leetcode-cn.com/problems/path-sum-iii

题目分析

  通过题意和示例我们了解到，这个路径的起点和终点无需是根结点或者叶子结点，那么很难用从上往下或者是从下往上传递的路径和。联想到我们做过的 求数组任意区间内元素之和 这样的题目（查询了一下是 Leetcode 303，没有在 Leetcode 上做过，是之前在程序设计的时候就做过，非常经典的题目）。我们的处理方法是不记录数组的每个数，而是直接记录数组到这个数的累加和，而区间和就是用区间右端点的累加和减去左端点的累加和，这样对于多次查询我们就不用再遍历进行累加。“累加和”我们也可以视为“前缀和”，也就是表达了数组从起点到这个数作为“前缀”的和。在这道题上，可不可以也把根结点到叶子结点的这段路径视为一个数组呢？这样任意一段路径的和也就是数组某一个区间的和，我们要找的也就是区间和为 targertSum 的区间数量。
  我们来思考一下树和数组中有什么不同。树中带有分叉，而不同分叉的也就不算做是一个路径了。我们如果使用深度优先搜索的遍历方式，维护的其实就是单条路径，那么我们可以使用回溯的方法，寻找完某一个结点后，将其从数组中删去，然后遍历别的结点，这样实时维护的就是一条路径而已。然后再次考虑一下，我们需要找到的是特定和的区间，而不是特定区间的和，我们遍历到某个结点时计算出当前的前缀和 preSum，需要知道的是前缀和为 preSum - targetSum 的区间是否存在（它们的差就是 targetSum 也即那段路径的和就是符合题意的），那么我们可以使用哈希表而不是数组进行记录，可以加快搜索速度。
  另外思考一个问题，在一条路径中，前缀和为某个数的区间是否可以不止一个？答案是可以的。因为结点值可以为负，那么应该存在某个和为 0 的区间，包含它们或者不包含它们的前缀和就是相同的。那我们使用哈希表记录某个前缀和是否存在的时候，应该同时记录它的数量，那我们就需要使用到 unordered_map 了。key 是前缀和，value 是数量。然后我们回溯删除的时候就把那个前缀和的数量减 1。
  答案我们是使用类的成员变量表示的，DFS 函数中传入父节点的前缀和，便于计算当前结点的前缀和，并将其加入到哈希表中。这里我们使用的是一个 if 语句先判断前缀和是否已存在，存在则数量加 1，遍历子节点后回溯减 1；不存在则创建并赋值为 1，遍历子节点后删除。
  后来看了一下别人的做法才了解到，unordered_map 的 value 值是有缺省值的，int 类型的就是 0，因此无需进行判断再插入的，这样的话一个前缀和不存在之后 value 值就会归为 0，而不会从哈希表中删掉，对于最后的结果也是没有影响的。
  而根结点也是可以作为路径中的点的，调用 DFS 从根结点中开始，根结点的“父节点”的前缀和我们认为是 0，那么也要将这个 0 先加入到哈希表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    int count = 0;
    unordered_map<int, int> preSum;

    void dfs(TreeNode *root, int pre, const int& targetSum){
        if(root == nullptr) return;

        int newpre = pre + root->val;
        if(preSum.find(newpre - targetSum) != preSum.end()){
            count += preSum[newpre - targetSum];
        }
        
        if(preSum.find(newpre) != preSum.end()){
            preSum[newpre]++;
            dfs(root->left, newpre, targetSum);
            dfs(root->right, newpre, targetSum);
            preSum[newpre]--; 
        }
        else{
            preSum[newpre] = 1;
            dfs(root->left, newpre, targetSum);
            dfs(root->right, newpre, targetSum);
            preSum.erase(newpre);
        }
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return 0;
        preSum[0] = 1;
        dfs(root, 0, targetSum);
        return count;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。我们对二叉树进行了一次 DFS 遍历，而查询和插入哈希表的操作都是 $O(1)$ 的。
  空间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。当二叉树是一条链时栈的深度达到了 $n$，并且哈希表记录的也是整条路径中每个结点的前缀和，大小也会达到 $n$。