437. 路径总和 III

短命女 2022-10-07 08:58 121阅读 0赞

> 给定一个二叉树，它的每个结点都存放着一个整数值。
> 
> 找出路径和等于给定数值的**路径总数**。
> 
> 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70 1][]

class Solution {
        int count=0;//结果
        public int pathSum(TreeNode root, int targetSum) {
            /**
            递归dfs+前缀和( 当前节点到-> 根节点的和)
             */
            HashMap<Integer,Integer> map=new HashMap();//存的是前缀和,以及他出现的次数
             if(root==null){
                 return 0;
             }
             map.put(0,1);//前缀和0 的有1个(根节点)
             dfs(root,0,map,targetSum);
            
             return count;
             
    
        }
    
        public void  dfs(TreeNode node,int preSum,HashMap<Integer,Integer> map,int target){
            if(node==null){
                return ;
            }
            
            preSum+=node.val;//当前前缀和( 当前节点到-> 根节点的和)
             
            count+=map.getOrDefault(preSum-target,0);//如果preSum-target有次数,说明从某一个节点到当前节点 可以凑成 target
            map.put(preSum,map.getOrDefault(preSum,0)+1);
            //递归  进入下层
            dfs(node.left,preSum,map,target);
            dfs(node.right,preSum,map,target);
            //回溯  回到上层
             map.put(preSum,map.getOrDefault(preSum,0)-1);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/94b5850f145641c18436050f326eebc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70 1]: /images/20221005/4d073a0da9f143fda2f8e092c2d0e4ed.png