leetcode437. 路径总和 III

1.题目描述：

给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于targetSum的 路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

2.递归：

深度优先搜索，解这道题需要先会leetcode112. 路径总和，在112题目的基础上，这道题目增加了两个条件：①、统计路径之和相等的路径数目。②、路径不一定从根节点开始，叶子节点终止。首先第一个问题较容易解答，在判断路径时同时计数即可，同时在hasPathSum方法中去除叶子节点的if判断，这里可以不返回值，原题代码使用return逻辑或若在左边已经找到为true，右子树不会继续判断，count计数偏小，并且在if(root.val == targetSum)中若返回true也会导致count偏小（比如1，2，3路径和1，2，3，-1，1路径）。时间复杂度O(n ^ 2)，空间复杂度O(n)。修改的代码如下：

private int count;
public void hasPathSum(TreeNode root,int targetSum){
        if(root == null) return;
        if(root.val == targetSum){
            count++;
        }
        hasPathSum(root.left,targetSum - root.val);
        hasPathSum(root.right,targetSum - root.val);
}

第二个问题，路径d不从根节点开始，则可以递归判断，我采用了前序遍历来依次累计路径个数，完整代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int count;
    public int pathSum(TreeNode root,int targetSum) {
        if(root == null) return 0;
        preOrder(root,targetSum);
        return count;
    }
    public void hasPathSum(TreeNode root,int targetSum){
        if(root == null) return;
        if(root.val == targetSum) count++;
        hasPathSum(root.left,targetSum - root.val);
        hasPathSum(root.right,targetSum - root.val);
    }
    public void preOrder(TreeNode root,int targetSum){
        hasPathSum(root,targetSum);
        if(root.left != null) preOrder(root.left,targetSum);
        if(root.right != null) preOrder(root.right,targetSum);
    }
}

修改一下，把前序遍历的递归过程方法放入pathSum方法中，hasPathSum方法返回值改为int类型：

class Solution {
    public int pathSum(TreeNode root,int targetSum) {
    if(root == null) return 0;
    return hasPathSum(root,targetSum) + pathSum(root.left,targetSum) + pathSum(root.right,targetSum);//直接往左右子节点递归
    }
    private int hasPathSum(TreeNode root,int targetSum) {
        if(root == null) return 0;
        int count = 0;
        if(root.val == targetSum) count++;
        count += hasPathSum(root.left,targetSum - root.val) + hasPathSum(root.right,targetSum - root.val);
        return count;
    }
}

3.前缀和方法：

只需要依次遍历树的所有节点，时间空间复杂度均为O(n)。主要通过两个前缀和的差值为targetSum，并用哈希表记录满足条件的前缀和频次来计数，代码理解不太容易理解：

class Solution {
    private int res;
    public int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> preMap = new HashMap<>();//记录路径中某个前缀和出现的次数
        preMap.put(0, 1);//根节点的前缀信息也记录在里面，包含路径仅为根节点的情况
        dfs(root, preMap, 0, targetSum);
        return res;
    }
    public void dfs(TreeNode root, Map<Integer, Integer> preMap, int curr, int targetSum) {
        if (root == null) return;//递归结束条件
        //每级递归需要做的：
        curr += root.val;//计算前缀和
        res += preMap.getOrDefault(curr - targetSum, 0);//累计符合条件的前缀和
        preMap.put(curr, preMap.getOrDefault(curr, 0) + 1);//记录当前前缀和，与上一步顺序不能颠倒
        dfs(root.left, preMap, curr, targetSum);
        dfs(root.right, preMap, curr, targetSum);
        preMap.put(curr, preMap.getOrDefault(curr, 0) - 1);//去除当前层前缀信息，保证路径严格自上而下
    }
}