LeetCode437 路径总和III

题目

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

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

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

提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109 
-1000 <= targetSum <= 1000 

方法

深度优先遍历法

• 时间复杂度：O（n^2），n为二叉树节点个数
• 空间复杂度：O（n）

class Solution {
    private int count = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        int count = chooseRoot(root,targetSum);
        count += pathSum(root.left,targetSum);
        count += pathSum(root.right,targetSum);
        return count;
    }
    private int chooseRoot(TreeNode root,int targetSum){
        int count = 0;
        if(root == null){
            return 0;
        }
        if(root.val==targetSum){
            count++;
        }
        count += chooseRoot(root.left,targetSum-root.val);
        count += chooseRoot(root.right,targetSum-root.val);
        return count;
    }
}

前缀和+前序遍历法

若一维数组中两个节点（不一定相邻）的前缀和之差等于targetSum，则说明两个节点之间的路径和为targetSum，利用这一原理，我们可以求从根节点到不同叶子节点的某条路径下不同节点的前缀和之差等于targetSum的并记数，即若当前前缀和curr-targetSum的值是之前访问过的父节点的前缀和，则说明该父节点到当前节点为一个符合路径。

• 时间复杂度：O（n），n为二叉树节点个数
• 空间复杂度：O（n）

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map profixsum = new HashMap<>();
        profixsum.put(0L,1);
        return dfs(root,targetSum,profixsum,0L);
    }
    private int dfs(TreeNode root,int targetSum,Map profixsum,Long curr){
        if(root==null) return 0;
        curr += root.val;
        //求之前已满足前缀和为curr-targetSum的父节点个数
        int count = profixsum.getOrDefault(curr-targetSum,0);
        //把当前节点加入前缀和map中，然后往下访问子节点
        profixsum.put(curr,profixsum.getOrDefault(curr,0)+1);
        count += dfs(root.left,targetSum,profixsum,curr);
        count += dfs(root.right,targetSum,profixsum,curr);
        //左右子节点访问完后删去当前root节点的前缀和回到root的父节点
        profixsum.put(curr,profixsum.getOrDefault(curr,0)-1);
        return count;
    }
}