[LeetCode] 129. Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

Leetcode - Sum Root to Leaf Numbers

문제 유형 : dfs, 이진트리

문제 난이도 : Medium

 

문제

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

 

0~9의 값을 가진 이진 트리의 루트가 주어집니다.

루트부터 리프 노드 까지의 경로를 그대로 숫자로 변환했을 때의 합을 모두 구하시오.

 

풀이

함수를 새로 만들어서, 루트와 경로를 인수로 받게 하도록 합니다.

함수를 호출할 때, 현재 서브트리의 루트를 경로에 포함시키도록 합니다.

 

현재 서브트리의 루트가 리프라면, 경로를 반환합니다.

아니라면, 각각 왼쪽과 오른쪽 자식을 재귀호출한 값의 합을 반환합니다.

 

 

코드

C++

trace를 문자열로 했는데, 기존 숫자에 10을 곱한 값에 현재 노드값을 더하는 방법도 있다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getSum(string trace, TreeNode* root) {

        if(root -> left == NULL && root -> right == NULL) {
            return stoi(trace);
        }

        int left = 0;
        if(root -> left != NULL) {
            left = getSum(trace + to_string(root -> left -> val), root -> left);
        }

        int right = 0;
        if(root -> right != NULL) {
            right = getSum(trace + to_string(root -> right -> val), root -> right);
        }

        return left + right;
    }

    int sumNumbers(TreeNode* root) {
        return getSum(to_string(root -> val), root);
    }
};