题目：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：遍历出树的所有路径，然后将这些路径的和相加，该解析方法和 path sum ii 那道题目解析2方法很像(http://blog.csdn.net/weishenmetlc/article/details/61209222)，因为都要遍历出所有路径， 代码如下：
// 递归法，时间复杂度 O(n)，空间复杂度 O(logn) class Solution { public: int sumNumbers(TreeNode* root) { int sum = 0; int tmp = 0; sumNumbers(root, tmp, sum); return sum; } private: void sumNumbers(TreeNode* root, int& tmp, int& sum) { if (!root) return; tmp = tmp * 10 + root -> val; if (!root -> left && !root -> right) sum += tmp; sumNumbers(root -> left, tmp, sum); sumNumbers(root -> right, tmp, sum); tmp /= 10; } };解析2：先求出从根节点到其左子树的所有路径和，再求出从根节点到其右子树的所有路径和，相比如解析1， 该方法更易理解，代码如下：
下面代码的思想及编写参考了网址https://github.com/soulmachine/leetcode#leetcode题解题目
// 递归法，时间复杂度 O(n)，空间复杂度 O(logn) class Solution { public: int sumNumbers(TreeNode* root) { return dfs(root, 0); } private: int dfs(TreeNode* root, int sum) { if (!root) return 0; if (!root -> left && !root -> right) return 10 * sum + root -> val; return dfs(root -> left, sum * 10 + root -> val) + dfs(root -> right, sum * 10 + root -> val); } };