LeetCode (C/C++) 129. Sum Root to Leaf Numbers

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

 

 

---

풀이

현재 노드까지의 합을 저장하고, 자식 노드를 탐색할 때 이 합을 전달해주는 방식으로 풀었다.

트리 탐색이라 BFS, DFS 둘 다 될 것 같아서 두 방법 다 풀어보았다.

DFS가 조금 빠른 것 같아 보였지만 이 정도의 차이는 유의미하지 않다고 들어서 큰 차이는 없을 것 같다.

---

코드 1 - BFS

6ms, 11.4MB

typedef pair<TreeNode*, int> node;
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        queue <node> Q;
        int sum = 0;

        // 현재 노드와 현재 노드까지의 합을 큐에 저장
        Q.push({root, 0});
        while (!Q.empty()) {
            TreeNode* nowRoot = Q.front().first;
            int nowSum = Q.front().second;

            Q.pop();

            // 현재 노드까지의 합을 계산 후 저장
            nowSum = nowSum * 10 + nowRoot->val;

            // leaf node라면 현재 노드까지의 합을 전체 합에 더함
            if (!nowRoot->left && !nowRoot->right) {
                printf("nowSum : %d\n", nowSum);
                sum += nowSum;
                continue;
            }

            // 자식 노드가 있다면 자식노드와 현재까지의 합을 큐에 저장
            if (nowRoot->left)
                Q.push({nowRoot->left, nowSum});
            if (nowRoot->right)
                Q.push({nowRoot->right, nowSum});
        }
        return sum;
    }
};

 

코드2 - DFS

0ms, 10.9MB

typedef pair<TreeNode*, int> node;
class Solution {
public:
    
    int getSum(TreeNode *root, int nowSum) {
        
        int total = 0;
        
        // 현재노드까지의 값 갱신
        nowSum = nowSum * 10 + root->val;

        // 자식 노드가 없다면 현재까지의 합 반환
        if (!root->left && !root->right)
            return nowSum;
        
        // 자식이 있다면 현재까지의 합을 가지고 자식 노드를 탐색
        if (root->left)
            total += getSum(root->left, nowSum);
        
        if (root->right)
            total += getSum(root->right, nowSum);

        return total;
    }
    
    int sumNumbers(TreeNode* root) {
      return getSum(root, 0);
    }
};