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
.
题目解析:
还是递归求解,当递归的时候,传入这一层计算的结果值,供下层计算。当叶节点的时候,才能就保存退出。不能左子树或右子树为空,保存退出,这样会重复计算!考虑时候应该想全面一些。
class Solution { public: int sumNumbers(TreeNode *root) { if(root == NULL) return 0; int res = 0; countSum(root,0); for(int i = 0;i < arr.size();i++) res += arr[i]; return res; } void countSum(TreeNode *root,int sum){ sum = sum*10 + root->val; if(root->left == NULL && root->right == NULL){ arr.push_back(sum); return ; } if(root->left) countSum(root->left,sum); if(root->right) countSum(root->right,sum); } private: vector<int> arr; };