c++ - “总和叶数”问题的解决方案
问题描述
给定一棵仅包含 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;
}
解决方案
线
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;
}