решение проблемы "суммировать числа от корня до листа"

Question

Учитывая двоичное дерево, содержащее только цифры от 0-9, каждый путь от корня к листу может представлять число.

Примером является путь от корня к листу 1-> 2-> 3который представляет число 123.

Найти общую сумму всех корневых чисел% 1003.

пример:если 1 является корнем, его левый потомок равен 2, а правый потомок равен 3,Путь от корня к листу 1-> 2 представляет число 12.
Путь от корня к листу 1-> 3 представляет число 13.

Возврат суммы = (12 + 13)% 1003 = 25% 1003 = 25.Оригинальная проблема здесь

PS: это не домашняя работа, я готовлюсь к поступлению в колледж.моя попытка:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void DFS(TreeNode* root, string &temp, int *ans){
    if(!root)
    return;

    temp = temp + to_string(root->val);

    if(root->left == NULL && root->right == NULL && temp.length()!=0){
        *ans = (*ans + stoi(temp))%1003;
    }

    if(!root->left)
    DFS(root->left, temp, ans);
    if(!root->right)
    DFS(root->right, temp, ans);

    if(!temp.empty())
    temp.pop_back();
} 
int Solution::sumNumbers(TreeNode* A) {
    string temp = "";
    int ans = 0;
    DFS(A, temp, &ans);
    return ans%1003;
}

Answer 1

Строка

if(!root->left) DFS(root->left, temp, ans); должна быть

if(root->left) DFS(root->left, temp, ans);

То же самое для правого узла.По сути, вы никогда не спускаетесь в дерево, если узел существует.

---

В качестве альтернативы вы можете упростить код:

• Используйте целые числа вместо строк, чтобы сделать вычисления легче,
• Передача temp переменной за копией, тогда вам не нужно будет "pop_back" последней цифры.
• Вызов DFS без проверки, равен ли указатель нулю, так как он уже проверяет наначало.
• Удалить последнюю операцию по модулю, поскольку она уже была выполнена в DFS.

void DFS(TreeNode* root, int temp, int *ans){
    if(!root)
        return;

    temp = temp*10 + root->val;

    if(!root->left && !root->right)
        *ans = (*ans + temp)%1003;

    DFS(root->left, temp, ans);
    DFS(root->right, temp, ans);
} 
int Solution::sumNumbers(TreeNode* A) {
    int ans = 0;
    DFS(A, 0, &ans);
    return ans;
}