/**
 * 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 {
    // 경로를 따라 모든 값을 더하여 targetSum과 같은 루트-리프 경로가 존재하는지 체크
    // O(n)
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 종료조건: 더 이상 처리할 노드가 없다.
        if (root == null) return false;
        
        // leaf node case: 자식이 없고 현재노드 값이 타겟값과 같을 경우
        if (root.left == null && root.right == null && root.val == targetSum) return true;
        
        // 현재노드 값만큼 빼고 자식 노드로 처리를 넘긴다.
        targetSum -= root.val;

        // 왼쪽 또는 오른쪽 노드 체크
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }
}