Path Sum

💬 문제

[문제 링크]

특정 트리의 시작 노드인 root
root에서부터 leaf까지의 합이 targetSum인
path가 있다면 true 반환, 아니라면 false 반환

✍️ 나의 풀이

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if (root === null) 
        return false;
  
    targetSum -= root.val;
    if (root.left === null && root.right === null)
        return targetSum === 0;
  
    let left = hasPathSum(root.left, targetSum);
    let right = hasPathSum(root.right, targetSum);
  
    return left || right;
};

현재 노드의 값을 targetSum에서 빼고 다음으로 넘어감
만약 현재 노드가 leaf라면 targetSum이 0이 되었는지 결과 반환
leaf가 아니라면 왼쪽 자식, 오른쪽 자식으로 가는 path를 재귀로 확인하고
둘 중 하나라도 true가 반환되면 첫 호출된 함수로 계속해서 true 반환

📌 결과

Accepted
Runtime 60ms (Beats 66.10%)
Memory 51.25MB (Beats 94.94%)

📚 러닝 포인트

path를 찾는 문제이기 때문에 DFS를 사용했다. 처음에는 재귀 함수를 따로 만들어서 sum을 쌓아가는 방식으로 구현했었는데, 테스트에서 몇 가지 고려해야할 점을 발견했다. root.val === targetSum일 때 root의 자식이 없어서 root==leaf라면 true이지만, 어느 쪽이라도 자식이 있다면 root!=leaf이기 때문에 false를 반환해야 한다. 그래서 leaf 판단을 다음 자식으로 넘어가서 null이라면 leaf라고 구현했는데, 넘어가지 않고 판단하는 것으로 바꾸게 되었다. 그러고 나니 훨씬 코드가 깔끔해져서 럭키비키잖아~🍀