"sum root to leaf numbers" 问题的解决方案

Question

给定一棵仅包含 0-9 数字的二叉树，每个 root-to-leaf 路径可以代表一个数字。

例如 root-to-leaf 路径 1->2->3 表示数字 123。

求所有root-to-leaf个数字的总和%1003。

示例：
如果 1 是根，它的左 child 是 2，右 child 是 3 那么，
root-to-leaf路径1->2表示数字12。
root-to-leaf路径1->3表示数字13。

Return 总和 = (12 + 13) % 1003 = 25 % 1003 = 25.
原题is here

P.S: 这不是作业，我在准备大学实习。我的尝试：

/**
 * 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;
}

"sum root to leaf numbers" 问题的解决方案

solution to "sum root to leaf numbers" problem

c++

binary-tree