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.
思路：最近睡得不好，搞得脑子也短路了。一直想着怎么从叶节点往上获取数字。费了好大的劲才AC了，结果一看答案，立马郁闷了。不到10行就能搞定。
具体的原理是深度优先，在向下迭代的过程中，用一个变量不断的把父节点以上的数字传下来，返回的时候把结果加起来。
public int sumNumbers(TreeNode root) {
return helper(root, );
}
public int helper(TreeNode root, int curSum) {
if(root == null) return ;
curSum = curSum* + root.val;
if(root.left == null && root.right == null) return curSum;
return helper(root.left, curSum) + helper(root.right, curSum);
}
下面是我自己AC的代码，超长，超繁琐，当个反面例子吧。思路是把每个数字都存在一个vector里面。之所以繁琐是因为我只是在返回的时候下功夫。
int sumNumbers(TreeNode *root) {
int s, e, sum = ;
vector<vector<int>> v;
Numbers(root, s, e, v);
for(vector<vector<int>>::iterator it = v.begin(); it != v.end(); ++it)
{
int num = ;
while(!it->empty())
{
num = num * + it->back();
it->pop_back();
}
sum += num;
}
return sum;
}
void Numbers(TreeNode * root, int &s, int &e, vector<vector<int>>& v)
{
int sl = -, el = -, sr = -, er = -;
s = e = -;
if(root == NULL) return;
if(root->left == NULL && root->right == NULL) //在叶节点 压入新的数字
{
e = s = v.size();
v.push_back(vector<int>(,root->val));
return;
}
if(root->left != NULL)
{
Numbers(root->left, sl, el, v);
for(int i = sl; i <= el; ++i)
{
v[i].push_back(root->val);
}
s = sl; e = el;
}
if(root->right != NULL)
{
Numbers(root->right, sr, er, v);
for(int i = sr; i <= er; ++i)
{
v[i].push_back(root->val);
}
s = (s == -) ? sr : s;
e = er;
}
}