23.03.14. 풀었던 문제들

Leetcode 129. Sum Root to Leaf Numbers

 각 vertex에서 값 : 이전 vertex 값 * 10 + 현재 vertex 값

 이 조건으로 모든 leaf node의 값의 합을 구하는 문제이다.

 

 문제를 처음 보고 함수에 추가 인자를 넣고 싶지 않아 처음에는 tree traversal로, leaf부터 올라오면 안되나? 생각했다. 그러나 이렇게 풀면 마땅한 방법이 없다. 추가 공간을 써야 하기도 하고.

 그래서 그냥 함수에 추가 인자를 하나 넣고 풀었다. DFS()함수는 아래와 같은 역할을 한다.

• 현 vertex의 값을 구한다.(prev * 10 + cur->val)
• 현 vertex가 leaf면 전역변수 sum에 값을 더해줌
• leaf가 아니라면 left, right를 탐색함

 그리고 main함수에서 DFS(root, 0)을 호출하면 끝이다. 그리 어렵진 않은 간단한 tree 순회 문제.

 

 만약 입력이 long long같이 매우 큰 경우라면 int 대신 long이나 string을 쓰면 될 것이다.

// Runtime 3 ms Beats 62.17%
// Memory 9.2 MB Beats 52.62%

class Solution {
public:
    int sum = 0;
    void DFS(TreeNode *cur, int prev){
        // calculate current value using prev value
        int suffixSum = 10 * prev + cur->val;

        // base case : leaf
        if(cur->left == NULL && cur->right == NULL){
            sum += suffixSum;
            return;
        }

        // not leaf, then deeper
        if(cur->left) DFS(cur->left, suffixSum);
        if(cur->right) DFS(cur->right, suffixSum);
    }
    int sumNumbers(TreeNode* root) {
        DFS(root, 0);
        return sum;
    }
};

 

시간복잡도

 모든 vertex를 순회하는 DFS이므로 O(n)이다.

 

공간복잡도

 tree height만큼 stack이 쌓이므로 O(h)이다. 주어진 binary tree가 balanced라는 조건은 없으므로 worst case O(n)이다.