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);}
}