题意

给定一颗二叉树，每个节点上有一个数字，计算每一条从根节点到叶子节点的路径组成的数字的和。

思路

由于二叉树的左右子树也都是二叉树，我们只需要对其递归操作就能得到结果，这里我们使用深度优先搜索的方法，从根节点开始，分别计算左右子树路径和，每到一个叶子节点说明已经找到了一条路径，将总和$sumTotsumTot$加上这次的路径值，最后就能得到结果。

例如对于如图二叉树，根节点为1，其右子树的路径为$1-3-71-3-7$,故右子树路径和就是137，左子树有两条路径分别为$1-2-4-51-2-4-5$和$1-2-4-61-2-4-6$,故左子树路径和为1245+1246=2491,答案即为2628。

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int dfs(TreeNode* now,int sumTot)
    {
        if(now == NULL) return 0;//若当前节点不存在返回0
        int sumNow = 10 * sumTot + now->val;//计算当前的路径值
        if(now->left == NULL && now->right == NULL)
            return sumNow;//到达叶子节点，返回该条路径值
        return dfs(now->left,sumNow)+dfs(now->right,sumNow);//未到达叶子结点，继续搜索
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);//从根节点开始搜索
    }
};

复杂度分析

时间复杂度：$O(n)O(n)$,$nn$是二叉树的节点个数，每个节点都一定遍历到了一次。

空间复杂度：$O(n)O(n)$,为深度优先搜索所用栈空间。