Sum Root To Leaf Numbers

129. 求根节点到叶节点数字之和

分析

递归遍历二叉树：使用深度优先搜索遍历树，从根节点开始，到达每个叶节点时，记录下从根到当前节点的路径形成的数字
路径数字的累加：在遍历过程中，将当前节点的值添加到路径上，形成当前路径的数字。在到达叶节点时，将该数字加入总和
返回结果：最终返回计算得到的所有路径之和

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(h)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution
{
public:
    int sumNumbers(TreeNode* root)
    {
        int res = 0;
        // 如果根节点非空，开始递归
        if (root)
            dfs(root, res, 0);
        return res;
    }

    void dfs(TreeNode* root, int& res, int cur)
    {
        // 将当前节点的值加到当前路径的数字中
        cur = cur * 10 + root->val;

        // 如果当前节点是叶节点，将路径数字加到结果中
        if (!root->left && !root->right)
            res += cur;

        // 继续递归遍历左子树
        if (root->left)
            dfs(root->left, res, cur);

        // 继续递归遍历右子树
        if (root->right)
            dfs(root->right, res, cur);
    }
};