题目：二叉树根节点到叶子节点的所有路径和

描述：给定一个仅包含数字0−9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。例如根节点到叶子节点的一条路径是1→2→3,那么这条路径就用123来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：这颗二叉树一共有两条路径，根节点到叶子节点的路径1→2用数字12代替，根节点到叶子节点的路径1→3用数字13代替，所以答案为12+13=25。

示例1：输入：{1,0}，返回值：10


解法一：

思路分析：通过题目分析，我们可以将每条根节点到叶子结点的路径和用一个数字代替，如果向下一个结点，就将之前的数字都左移一位，通过使用dfs找到左右子树的所有路径，最后回溯求和，得到最后的结果值。

实例分析：根节点到叶子节点的一条路径是1→2→3。

数字

1

2

3

sum = sum * 10 + root->val;

第一步

Sum = 0 * 10 + 1

第二步

判断2和3结点是否为1的子结点

第三步

Sum = 1 * 10 + 2 + 1 * 10 + 3 = 25

最后输出结果值为25

具体C++代码为： 


/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        // write code here
        if(!root)//特殊情况
            return 0;
        int sum = 0;
        return preorder(root, sum);
    }
    
    int preorder(TreeNode* root, int sum){
        if(root == NULL)
            return 0;
        sum = sum * 10 + root->val;//一层一层进行遍历
        if(!root->left && !root->right)//没有子结点
            return sum;
        return preorder(root->left, sum) + preorder(root->right, sum);
    }
};


递归遍历二叉树中的结点，其时间复杂度为O(N)，空间复杂度为O(1)。
解法二：

思路分析：我们也可以通过在vector中保存路径来计算结果，将根节点到叶子节点的路径记录到paths中，通过计算得到最终的结果。

具体C++代码如下所示： 

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        // 通过在vector中保存路径来计算结果
        if(root == nullptr)
            return 0;
        vector temp;
        vector paths;
        path(temp, root, paths);
        //对paths里记录的内容进行求和
        int sum = 0; //最终结果
        for(auto &i : paths){
            int line = 0; //记录单个路径的和
            for(auto &j : i){
                line = line*10+j;
            }
            sum += line;
        }
        return sum;
    }
    
    void path(vector&temp, TreeNode* root, vector &paths){
        if(root == nullptr) 
            return;
        temp.push_back(root->val);
        if(root->left==nullptr && root->right==nullptr)
            paths.push_back(temp); //将根节点到叶子节点的一个路径记录到paths中
        if(root->left)
            path(temp, root->left, paths);
        if(root->right)
            path(temp, root->right, paths);
        temp.pop_back();
    }
};
通过 vector中保存路径来计算结果，要循环计算单个路径的和，所以其时间复杂度最大为O(N)，空间复杂度为O(N)。