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.
这道题的要求是统计所有根到叶子节点路径上的数字和，例如根到叶子的路径是1->2->3，则这个数字是就是123。
深搜，用全局变量sum记录总和，形参n表示到达当前节点时已经形成的数字，所以再加上当前节点后就为n*10+p->val。然后当遇到叶子节点是，就把n累加到sum中。剩下的就是递归进行搜索子节点。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
int sum = 0;
public:
int sumNumbers(TreeNode *root)
{
if(root == NULL)
return 0;
sumNumbers(root, 0);
return sum;
}
private:
void sumNumbers(TreeNode *p, int n)
{
n = n * 10 + p -> val;
if(p -> left == NULL && p -> right == NULL)
{
sum += n;
return;
}
if(p -> left != NULL)
sumNumbers(p -> left, n);
if(p -> right != NULL)
sumNumbers(p -> right, n);
}
};