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.
递归前序遍历树，并记录经过的数值，当到达叶子时，保存值到vector中, 然后求vector的值即可.
static inline bool isLeaf(TreeNode *root)
{
return root->left == NULL && root->right == NULL;
}
class Solution {
public:
int sumNumbers(TreeNode *root) {
if (root == NULL)
return 0;
vector<int> numbers;
getNumbers(numbers, root, 0);
int sum = 0;
for_each(numbers.begin(), numbers.end(), [&sum](int value){sum += value;});
return sum;
}
private:
void getNumbers(vector<int> &result, TreeNode *root, int number) {
if (root == NULL)
return;
number *= 10;
number += root->val;
if (isLeaf(root)) {
result.push_back(number);
} else {
getNumbers(result, root->left, number);
getNumbers(result, root->right, number);
}
}
};以上方法的时间空间复杂度都是O(n)。
时间是不可能优化的，关键空间，我们可以不保存值，直接求解。
class Solution {
public:
int sumNumbers(TreeNode *root) {
return sumNumbers(root, 0);
}
private:
int sumNumbers(TreeNode *root, int sum) {
if (root == NULL)
return 0;
sum = sum * 10 + root->val;
if (isLeaf(root)) {
return sum;
} else {
return sumNumbers(root->left, sum) + sumNumbers(root->right, sum);
}
}
};此时空间复杂度为O(1).