[LeetCode] 112. Path Sum

Lucid·2021년 2월 25일
1
post-thumbnail

문제

https://leetcode.com/problems/path-sum/

문제 접근 및 풀이

내가 root부터 leaf까지 더해서 targetSum이 있는가를 확인하는 문제였다.
내가 leaf 노드일때 현재 계산한 값이 0인지 확인해주어서 접근하였다.

간단 슈도코드

- 있니 없니? 확인하는 문제
- 내가 null 인가 ? -> false 반환 (여기까지 왔다는 건 이미 조건에 부합하지 않다는 것)
- 계산
- 내가 leaf이고 target이 0 이냐 true 반환
- 어쨌든 true가 하나만 있으면 됨 (or로 비교)

결과


const hasPathSum = (root, targetSum) => {
  if (root === null) return false;

  const calValue = targetSum - root.val;
  if (root.left === null && root.right === null) {
    if (calValue === 0) return true;
    return false;
  }

  return hasPathSum(root.left, calValue) || hasPathSum(root.right, calValue);
};

사담

뭔가 이제 진짜 DFS의 시작인가 싶은 느낌의 문제였다. 정말 DFS의 예제 느낌 ㅎㅎ

profile
Find The Best Solution 😎

0개의 댓글