力扣 112.路径总和

这一题我开始的想法是把所有路径的结果保存到一个HashSet中，然后从HashSet里面查找是否存在目标元素，但是者个方法的遍历了所有的路径，实际上不需要遍历所有的路径，如果在每次到达叶子节点就判断当前路径的数值之和是否等于目标元素，就能减少遍历的次数。
有一个细节要注意：sum，flag不能定义成static，否则里面的值会被不同测试用例所共享，导致结果出错。

/**
 * 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 {
    private int sum=0;
    private boolean flag=false;
    private void myPath(TreeNode root, int targetSum){
        if(root==null)return;
        sum+=root.val;
        if(root.left==null && root.right==null){
            if(sum==targetSum)flag=true;
        }
        if(flag)return;
        if(root.left!=null){
            myPath(root.left,targetSum);
            //减去不符合的节点的值
            sum-=root.left.val;
        }
        if(root.right!=null){
            myPath(root.right,targetSum);
            //减去不符合的节点的值
            sum-=root.right.val;
        }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        myPath(root,targetSum);
        return flag;
    }
}