lc437.路径总和III

437. 路径总和 III

前后一共做了三次，每次都想不出来使用前缀和的方法。

思路1：DFS遍历

先序遍历整个二叉树，遍历到某一结点后，以该节点为子树，查找当前子树中，是否存在一条从根节点出发的路径，满足路径和条件。

复杂度分析：

• 时间复杂度：与DFS遍历不同的点，在于每到达一个节点都需要重新遍历子树，寻找备选最优解，时间复杂度为O(N^2)
• 空间复杂度：两次遍历不影响栈的深度，最大栈深度与DFS相同，空间复杂度为O(logN)

代码实现：

思路比较简单，实现也比较简单

public int getSolution(TreeNode curNode ,int curSum, int targetSum){
    int result = 0;
    if(curNode == null){
        return result;
    }
    curSum += curNode.val;
    if(curSum == targetSum){
        result++;
    }
    result += getSolution(curNode.left, curSum, targetSum) + getSolution(curNode.right, curSum, targetSum);
    return result;
}
public int pathSum(TreeNode root, int targetSum) {
    if(root == null){
        return 0;
    }
    //简单的dfs
    return getSolution(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}

思路2：前缀和

DFS计算路径和只能计算从根路径到当前节点的总和，但是满足目标解的路径不一定从根节点开始，我们可以将不从根节点开始的序列，转化成 两个从根出发序列的差，其中一个序列是另一个序列前缀。

如何实现这种存储，并且方便查询？深度遍历过程中将当前路径和存储到哈希表中，当遍历到某一个节点时，哈希表存储的是从根节点到当前节点的序列的所有前缀子序列的路径和,原问题转化为

$$sum_{seq\_i} = sum_{rootSeq_i} - sum_{preSeq_i}$$

在回退时，需要删除再是前缀的序列的前缀和（也就是当前序列）

复杂度分析：

• 时间复杂度：与DFS一致，时间复杂度为树中的节点数目，时间复杂度为O(N)
• 空间复杂度：哈希表的最大存储数量为O(logN)，空间复杂度为O(logN)

代码实现：

//前缀和算法，包含当前节点
public int dfs(TreeNode curNode,int curSum,int targetSum,Map<Integer, Integer> preSumMap){
    if(curNode == null){
        return 0;
    }
    int result = 0;
    curSum += curNode.val;
    if(preSumMap.containsKey(curSum - targetSum) && preSumMap.get(curSum - targetSum) != 0){
        result += preSumMap.get(curSum - targetSum);
    }
    //将当前前缀和添加到hashmap中
    int times = 1;
    if(preSumMap.containsKey(curSum)){
        times += preSumMap.get(curSum);
    }
    preSumMap.put(curSum, times);
    result += (dfs(curNode.left, curSum, targetSum, preSumMap) + dfs(curNode.right, curSum, targetSum, preSumMap));
    //回滚
    preSumMap.put(curSum, times - 1);
    return result;
}
public int pathSum(TreeNode root, int targetSum) {
    Map<Integer, Integer> preSumMap = new HashMap<>();
    preSumMap.put(0, 1);
    return dfs(root, 0, targetSum, preSumMap);
}

1. 初始化应加入根节点的”假”前缀序列(序列和为0)

   preSumMap.put(0, 1);

2. 有序树中可能有负值节点，不能只记录前缀值的否出现，应记录出现次数

   int times = 1;
   if(preSumMap.containsKey(curSum)){
   	times += preSumMap.get(curSum);
   }