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.
问题：给定一个二叉树，树的每个节点都只包含一个数字 0-9，将根节点到叶子节点路径上的元素值组合成一个整数，求所有整数和。
这是一道深度遍历的应用。深度遍历二叉树一般是递归遍历，或者借助栈遍历。每到达一个叶子节点，都需要重新遍历一次根节点到该叶子节点路径的值，借组栈遍历可以实现满足这个需要。
1 #define null_symble -2147483648 2 3 int sumNumbers(TreeNode* root) { 4 5 if(root == NULL){ 6 return 0; 7 } 8 9 list<TreeNode*> stackt; 10 stackt.push_back(root); 11 12 int sum = 0; 13 14 map<TreeNode*, int> node_val; 15 16 while(stackt.size() > 0){ 17 TreeNode* node = stackt.back(); 18 19 if(node->val != null_symble){ 20 node_val[node] = node->val; 21 node->val = null_symble; 22 } 23 24 if (node->left != NULL && node->left->val != null_symble){ 25 stackt.push_back(node->left); 26 continue; 27 } 28 29 if(node->right != NULL && node->right->val != null_symble){ 30 stackt.push_back(node->right); 31 continue; 32 } 33 34 if(node->left == NULL && node->right == NULL){ 35 string str = ""; 36 list<TreeNode*>::iterator l_iter; 37 for(l_iter = stackt.begin(); l_iter != stackt.end(); l_iter++){ 38 str += to_string(node_val[*l_iter]); 39 } 40 sum += stoi(str); 41 } 42 stackt.pop_back(); 43 } 44 45 return sum; 46 }
[LeetCode] 129. Sum Root to Leaf Numbers 解题思路
原文：http://www.cnblogs.com/TonyYPZhang/p/5117886.html