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

Question

给定一个二进制树，该二进制树只有0-9的数字，每个根到叶路径都可以代表一个数字。

一个示例是扎根路径1-> 2-> 3，代表数字123。

找到所有根到叶数量％1003的总和。

示例：
如果1是根，它的左孩子是2个，右孩子是3，则
根到叶路径1-> 2表示数字12。
根到叶路径1-> 3表示数字13。

返回sum =(12 13(％1003 = 25％1003 =25。
原始问题在这里

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，而无需检查指针是否为null，因为它已经在开始时检查了。
• 删除最后一个Modulo操作，因为它已经在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;
}