Sum Root to Leaf Numbers

💬 문제

[문제 링크]

특정 트리의 시작 노드인 root
각 root-to-leaf path 내 값을 문자열로 연결시킨 숫자를 다 더하여 반환

✍️ 나의 풀이

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    let sum = 0;
    var pathSum = function(node, num) {
        if (node === null)
            return ;

        num = num * 10 + node.val;

        if (node.left === null && node.right === null) {
            sum += num;
            return ;
        }

        pathSum(node.left, num);
        pathSum(node.right, num);
    }

    pathSum(root, 0);
    return sum;
};

재귀 함수 pathSum을 사용하여 leaf까지 이동
지금까지 만들어온 num에 10을 곱하여 자리 수 이동 후 현재 val 더하기
만약 왼쪽, 오른쪽 자식 둘 다 없다면 leaf이므로 전체 값을 더한 sum에 num 더하기
이후에 왼쪽, 오른쪽 모두 탐색하고 함수 종료
마지막으로 sum 반환하면 끝

📌 결과

Accepted
Runtime 44ms (Beats 96.41%)
Memory 49.31MB (Beats 85.01%)

📚 러닝 포인트

이번 문제도 바로 이전 문제와 매우 비슷해서 어렵지 않게 풀 수 있었다. path를 확인해야하므로 DFS를 사용하였고, 기억해야하는 변수(num)이 존재하기 때문에 따로 재귀 함수를 만들어주었다. 역시나 포인트는 leaf를 판단하는 것이기 때문에 양쪽 자식이 존재하지 않는 경우에만 값을 더해주는 조건을 걸어주어야 한다. 한쪽 자식만 존재하는 경우 반대쪽으로 넘어갔을 때 중복으로 값을 더하지 않도록 node === null일 때는 그냥 함수를 종료한다. 또한 숫자를 단순히 더하는게 아니라 이어나가야 하기 때문에 처음에는 문자열로 만들어서 leaf에서 parseInt 해주었는데, 생각해보니 10을 곱하여 자릿수 이동을 하면 가능한 것이어서 숫자로 바꾸었고, 결과 효율이 크게 상승했다.