leetcode 437.路径总和III

思路：其实说出来也就是一个深度优先搜索的问题而已。

我们可以首先遍历出树的全部结点，然后我们就从中一个一个拿出来进行深度优先搜索，也就是俗称的DFS。DFS的参数就定义为三个参数，一个参数用来存放结点，一个参数用来存放目前已经加了多少的和，还有目标和。

在DFS过程中，我们需要判断的条件无非有那么几个：首先就是本结点是不是空的，如果是就直接结束这个函数；如果我们目前加的和已经和目标i和相同了，我们就让全局变量cnt加1.

注意：有些人会问，为什么sum>targetSum不能作为终止条件呢？因为这里面的元素中会考虑负数的存在，我们如果目前和大于目标和了之后，要是后面有负数可以加上变成目标和，我们岂不是错过了这一种可能呢？所以这个不能作为条件。

还有就是结点有无的判断和是否是目标和的判断一定要分清先后，如果结点不存在在前，我们就需要先加上本结点的元素，然后判断目标和是否一致。

/**
 * 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 {
    int cnt=0;
    List<TreeNode>list=new ArrayList<>();
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null)
        return 0;
        qianxu(root);
        for(int i=0;i<list.size();i++){
            dfs(list.get(i),0,targetSum);
        }
        return cnt;
    }
    public void dfs(TreeNode t,long sum,int targetSum){
        if(t==null)
        return;
        sum+=t.val;
        if(sum==targetSum)
        cnt++;

        dfs(t.left,sum,targetSum);

        dfs(t.right,sum,targetSum);
        
    }
    public void qianxu(TreeNode t){
        if(t==null)
        return;
        list.add(t);
        qianxu(t.left);
        qianxu(t.right);
    }
}