LeetCode - path-sum (javascript)

리트코드 path-sum (easy) 풀이

문제링크

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

문제 해결 힌트

 - 재귀의 동작이 복잡해보이지만 결국 호출된 함수는 하나의 리턴값을 같는다는 것을 생각하자.

 - 주어진 hasPathSum을 이용하여 DFS를 구현한다.

문제 풀이 코드 

  var hasPathSum = function (root, sum) {
    if (!root) return false;

    if (!root.left && !root.right) {
      return sum === root.val;
    } else {
      return (
        hasPathSum(root.left, sum - root.val) ||
        hasPathSum(root.right, sum - root.val)
      );
    }
  };

시간복잡도: O(n)