题目：
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.
解题思路：
采用DFS，遍历二叉树，遇到叶子节点时，进行累加和，不多说，直接上代码。
实现代码：
#include <iostream>
#include <vector> using namespace std; /*
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) {}
* };
*/ struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; void addNode(TreeNode* &root, int val)
{
if(root == NULL)
{
TreeNode *node = new TreeNode(val);
root = node;
}
else if(root->val < val)
{
addNode(root->right, val);
}
else if(root->val > val)
{
addNode(root->left, val);
}
} void printTree(TreeNode *root)
{
if(root)
{
cout<<root->val<<" ";
printTree(root->left);
printTree(root->right);
}
}
class Solution {
public:
int sumNumbers(TreeNode *root) {
if(root == NULL)
return 0;
int sum = 0;
vector<int> v;
dfs(root, v, sum);
return sum;
} void dfs(TreeNode *node, vector<int> &v, int &sum)
{
if(node == NULL)
return ; v.push_back(node->val);
if(node->left == NULL && node->right == NULL)
{
vector<int>::iterator iter;
int tmp = 0;
for(iter = v.begin(); iter != v.end(); ++iter)
tmp =tmp*10 + *iter;
sum += tmp; }
else
{
if(node->left)
dfs(node->left, v, sum);
if(node->right)
dfs(node->right, v, sum);
}
v.pop_back(); }
};
int main(void)
{
TreeNode *root = new TreeNode(5);
addNode(root, 7);
addNode(root, 3);
addNode(root, 9);
addNode(root, 1);
printTree(root);
cout<<endl; Solution solution;
int sum = solution.sumNumbers(root);
cout<<sum<<endl;
return 0;
}