День 72: Суммируйте числа от корней до листьев

LeetCode 129. Суммировать числа от корня до листа

8ms

Временная сложность: O(n)

Пространственная сложность: O(n)

Рекурсивный вызов функции

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        if (!root) return res;
        
        DFS(root, res, root->val);
        
        return res;
    }
    
    void DFS(TreeNode* root, int& res, int cur) {
        if (!root) return;
        
        if (!root->left && !root->right) {
            res += cur;
        }
        
        if (root->left) {
            DFS(root->left, res, cur*10 + root->left->val);
        }
        
        if (root->right) {
            DFS(root->right, res, cur*10 + root->right->val);
        }
    }
};

Вначале я думал использовать string для отслеживания каждого пути, но передавать строку как копию везде очень дорого и делает программу очень медленной, 12 ms .

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        if (!root) return res;
        vector<string> sums;
        
        DFS(root, sums, to_string(root->val));
        
        for (string str : sums) {
            res += stoi(str);
        }
        
        return res;
    }
    
    void DFS(TreeNode* root, vector<string>& sums, string path) {
        if (!root) return;
        
        if (!root->left && !root->right) {
            sums.push_back(path);
        }
        
        if (root->left) {
            DFS(root->left, sums, path + to_string(root->left->val));
        }
        
        if (root->right) {
            DFS(root->right, sums, path + to_string(root->right->val));
        }
    }
};