题目描述

给定一棵二叉树，仅包含 0-9，每条从根节点到叶节点的路径表示一个整数。
例如，如果根节点到叶节点的路径是1->2->3，表示的数就是123。

请计算所有从根节点到叶节点的路径表示的数的和。

注意；叶节点指不包含儿子的节点。

样例1

输入：

[1,2,3]
    1
   / \
  2   3

输出：

25

解释：
总共有两条根到叶的路径：1->2和1->3，表示的数分别是12和13，所以总和是25。

样例2

输入：

[4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1

输出：

1026

解释：总共存在三条根到叶的路径：4->9->5, 4->9>1, 4->0，表示的数分别是495,491,40，总和是1026。

算法

(树的遍历) $O(n)$

从根节点递归遍历整棵树，遍历时维护从根节点到该节点的路径表示的数，当遍历到叶节点时，将路径表示的数累加到答案中。

时间复杂度分析：每个节点仅被遍历一遍，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0;

    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* u, int s)
    {
        if (!u) return ;
        s = s * 10 + u->val;
        if (u->left) dfs(u->left, s);
        if (u->right) dfs(u->right, s);
        if (!u->left && !u->right) ans += s;
    }
};