문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

이진 트리 root와 정수 targetSum이 주어졌을 때, root에서 leaf까지 경로에 있는 모든 값의 합이 targetSum과 같다면 rtue를 반환해라.
leaf는 자식이 없는 노드이다.

Example

#1

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Output: true
Explanation: targetSum과 같은 루트에서 리프까지의 경로가 표시되어 있다.

#2

Input: root = [1, 2, 3], targetSum = 5
Output: false
Explanation: 트리에서 루트에서 리프까지의 2개의 경로가 있다.
(1 --> 2): 합은 3이다.
(1 --> 3): 합은 4이다.
합이 5인 루트에서 리프까지의 경로는 없다.

#3
Input: root = [], targetSum = 0
Output: false
Explanation: 트리가 비어있으므로, 루트에서 리프까지의 경로는 존재하지 않는다.

Constraints

• 트리에 있는 노드의 수는 0에서 5000 범위에 있다.
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Solved

DFS를 사용하여 문제를 해결했다.
root부터 leaf까지 targetSum에서 노드의 값을 빼면서 탐색하여, leaf의 값과 targetSum이 같다면 true, 그렇지 않다면 false를 반환했다.

/**
 * 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 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;

        if(root.val == targetSum && root.left == null && root.right == null) return true;

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}