Given a binary tree containing digits from 0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2
represents the number 12
.
The root-to-leaf path 1->3
represents the number 13
.
Return the sum = 12 + 13 = 25
.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> path;
int sum;
void calcSumNumbers(TreeNode *root,int idx){
if (!root){
return;
}
if (path.size() != idx + 1){
path.resize(idx + 1);
}
path[idx++] = root->val;
if (!root->left && !root->right){
for(size_t i = 0; i < path.size(); i++){ //从后往前也OK,小心size_t溢出,尤其在逆向循环中
sum += path[i] * pow(10,path.size() -i - 1);
}
return;
}
calcSumNumbers(root->left,idx);
calcSumNumbers(root->right,idx);
}
int sumNumbers(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (!root){
return 0;
}
sum = 0;
calcSumNumbers(root,0);
return sum;
}
};
原文链接: https://www.cnblogs.com/kwill/archive/2013/02/26/2934307.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/78924
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!