LeetCode 437. 路径总和 III，比较简单的容易理解的方法

╰半橙微兮° 2023-07-20 10:46 169阅读 0赞

## 问题 ##

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

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

二叉树不超过1000个节点，且节点数值范围是 \[-1000000,1000000\] 的整数。

示例：

root = \[10,5,-3,3,2,null,11,3,-2,null,1\], sum = 8

10
     /  \
    5   -3

/ \\  
3 2 11  
/ \\  
3 -2 1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  \-3 -> 11

## 分析 ##

主要思路：以树上的每一个节点作为根节点，然后向每一条路径下累加，若等于目标数值，计数加一。

创建两个函数，helper1用来遍历树上的每一个节点，每一个节点都调用一次helper2，helper2则进行对以当前节点作为根节点的树的所有路径进行累加。  
创建两个函数，helper1用来遍历树上的每一个节点，每一个节点都调用一次helper2，helper2则进行对以当前节点作为根节点的树的所有路径进行累加。  
![image.png][]

首先以10为根节点，向下遍历所有路径，在对应的路径累加

![image.png][image.png 1]  
第一条路径累加完，发现没有目标值，此时需要返回上一节点，所以需要舍弃当前节点的值，所以会有temp-=root.val,然后遍历右节点  
![image.png][image.png 2]  
没有，节点接着上移，遍历右节点  
![image.png][image.png 3]  
发现最后两个节点能和根节点组成10->-3->1，计数器累加，这样一个节点作为根节点的遍历完成，之后再以每一个节点作为根节点，遍历这颗以此节点作为根节点的树，重复上面的操作，即可找到所有满足要求的路径总和。

再以下一个节点为根节点演示一下：  
![image.png][image.png 4]  
只管以5作为根节点的树，其他不管  
![image.png][image.png 5]  
5->3,满足条件，res++  
![image.png][image.png 6]  
5->2->1，满足条件，res++。  
至此，以第二个节点为根节点的子树遍历也完成了

## java完整代码 ##

class Solution { 
        int res=0,temp=0;
        public void helper1(TreeNode root,int sum){ 
            if(root==null)return;
            helper2(root,sum);//每个节点都作为根节点调用helper2
            helper1(root.left,sum);
            helper1(root.right,sum);
        }
        public void helper2(TreeNode root,int sum){ 
            if(root==null)return;
            temp+=root.val;//对当前路径上的树累加
            if(temp==sum)//遇到目标值，计数器累加
                res++;
            helper2(root.left,sum);//遍历左子树
            helper2(root.right,sum);//遍历右子树
            temp-=root.val;//当前节点的左右子树遍历完，需要减去当前节点值，计算其他路径
    
        }
        public int pathSum(TreeNode root, int sum) { 
            helper1(root,sum);
            return res;
        }
    }

[image.png]: /images/20230528/b87678f67cba48bc9c99263a17100d94.png
[image.png 1]: /images/20230528/4b5e864f16604636adb465f6b4346d1b.png
[image.png 2]: /images/20230528/c24131877fc942be9491e73064836a1e.png
[image.png 3]: /images/20230528/2f4719ffb2b749a48d7f7c3090aad0d1.png
[image.png 4]: /images/20230528/134160a19bf04861816e101e41319fc5.png
[image.png 5]: /images/20230528/7e70f611724347999bc005b4114399bb.png
[image.png 6]: /images/20230528/938e8222a5f1448289b7c4e4cfee5ba0.png