[LeetCode] 129. Sum Root to Leaf Numbers

문제 출처: https://leetcode.com/problems/sum-root-to-leaf-numbers/

Sum Root to Leaf Numbers - LeetCode

---

문제

0~9의 숫자를 포함하고 있는 이진 트리 root가 주어진다.

 

트리 안의 루트에서 말단까지의 경로가 숫자로 표현된다.

• 예를 들어, 루트에서 말단까지 경로가 1 -> 2 -> 3 이라면, 이는 숫자 123의 표현이다.

 

루트에서 말단까지 경로로 만들어지는 모든 숫자의 합을 반환하라. 테스트 케이스의 정답은 32비트 정수 범위 내의 숫자를 갖는다.

 

말단 노드는 자식이 없는 노드를 말한다. 

예제

Input: root = [1,2,3]
Output: 25

Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Input: root = [4,9,0,5,1]
Output: 1026

Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

---

풀이

트리 탐색 기법인 DFS를 활용하여 문제에 접근할 수 있습니다.

 

DFS는 노드에서 자식이 존재한다면, 형제 노드보다 자식을 우선적으로 탐색하기 때문에 문제 해결에 더 적합할 것이라 판단하였습니다.

 

코드를 작성하면 아래와 같습니다. 

function dfs(root, numberStr) {
    // 재귀 종료
    if (!root) { return; }
    
    numberStr += root.val;
    
    // 말단 노드 체크
    if(!root.left && !root.right) {
    	// 말단 노드라면, 더 이상 탐색할 필요X
    	// answer: 함수 외부에 선언된 변수
    	answer += Number(numberStr);
    } else {
    	// 말단 노드가 아니라면, 더 탐색해야 함
    	dfs(root.left, numberStr);
        dfs(root.right, numberStr);
    }
    
    return;
}

매개변수를 통해 루트 노드에서 현재 노드까지 경로에 있는 숫자들의 정보를 전달해 줍니다. 말단 노드에 도착했을 때, 이 정보를 이용하여 최종 결과에 더해져야 할 숫자를 확보할 수 있게 됩니다.

 

이 함수를 활용하여 답을 구하는 코드를 작성하면 다음과 같습니다.

var sumNumbers = function(root) {
    let answer = 0;
    
    function dfs(root, numberStr) {
        if (!root) { return; }

        numberStr += root.val;

        if(!root.left && !root.right) {
            answer += Number(numberStr);
        } else {
            dfs(root.left, numberStr);
            dfs(root.right, numberStr);
        }

        return;
	}
    
    dfs(root, "");
    
    return answer;
}

 

Github: 129.js

GitHub - opwe37/Algorithm-Study