class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) 
            || hasPathSum(root.right, targetSum - root.val);
    }
}

class Solution {
    boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        return _hasPathSum(root, targetSum);
    }
    public boolean _hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return targetSum == 0;
        if (root.left == null && root.right != null) {
            return _hasPathSum(root.right, targetSum - root.val);
        }
        if (root.left != null && root.right == null) {
            return _hasPathSum(root.left, targetSum - root.val);
        }
        return _hasPathSum(root.left, targetSum - root.val) 
            || _hasPathSum(root.right, targetSum - root.val);
    }
}