[Leetcode] 112. Path Sum - JS

https://leetcode.com/problems/path-sum/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진 트리의 root, 정수 targetSum이 주어질 때, 
루트에서 리프노드까지 모든 값을 더한 값과 targetSum이 같은 경우가 존재하면 true를 반환하라.

제한조건
--------------------
- 노드의 갯수는 0 ~ 5000이다.
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000

 

2. 접근 방법

접근방법
--------------------
재귀적으로 노드들을 순회하면서 현재까지의 합계를 전달하여
현재 노드의 left, right 둘다 자식 노드가 없을 때, 
현재까지의 합계가 targetSum과 같은지 판단

left가 존재하면 재귀함수를 left와 누적합으로 호출하고
right가 존재하면 재귀함수를 right와 누적합으로 호출한다.

각 자식 노드를 재귀적으로 호출하여 반환값이 true, false를 판단한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var hasPathSum = function(root, targetSum) {
    if (!root) {
        return false;
    }

    function rootToLeaf(node, currentSum) {
        currentSum += node.val;

        if (!node.left && !node.right) {
            return currentSum === targetSum;
        }

        let leftHasPath = node.left ? rootToLeaf(node.left, currentSum) : false;
        let rightHasPath = node.right ? rootToLeaf(node.right, currentSum) : false;

        return leftHasPath || rightHasPath;
    }

    return rootToLeaf(root, 0);

};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

리프노드까지 합을 계산하는 로직을 재귀함수로 호출하는데, 누적 합계값을 어떻게 전달해야할지 잘 떠오르지 않았다.

total 변수를 선언하고 while 반복문 안에서 재귀함수를 호출하는 O(n^2) 방식으로 접근하니 너무 어렵게 생각하는 것 같았다.

 

결국 GPT의 도움을 받아 재귀함수에 파라미터값으로 누적합계를 전달하는 방법을 알게됐다.

실제 웹 개발을 할 때는 순수함수로 짜기 위해 함수 내부에서는 함수 파라미터로 전달된 값을 사용하는 것에 익숙해져있는데,

이와 같이 재귀함수를 이용하면서 함수 외부 값인 targetSum을 사용하는 것이 익숙하지 않았다.

 

또한 재귀함수의 반환값을 boolean으로 해줘야할지.. number를 반환해서 그 값을 다시 비교할지 생각하기가 어려웠다.

이진트리 문제는 재귀함수 아니면 while 반복문으로 모든 노드를 순회하는 유형이 자주 등장하니 이에 익숙해져야겠다.