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

本文最后更新于：2021年1月26日 下午

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

Solution

方法同 [113 路径总和 II]

  • 深度优先搜索
  • LeetCode官方，保存父节点的“值”，简洁很多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int dfs(TreeNode* root, int preSum){
        if(root==nullptr) return 0;
        int sum = preSum*10 + root->val;

        if(root->left==nullptr && root->right==nullptr)
            return sum;
        else
            return dfs(root->left, sum) + dfs(root->right, sum);
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};
  • 存储了路径节点，最后求“值”
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> path;

    void dfs(TreeNode* root){
        if(root==nullptr) return;
        path.push_back(root->val);

        if(root->left==nullptr && root->right==nullptr){
            int sum = 0;
            for(int& num : path){
                sum = sum*10 + num;
            }
            res.push_back(sum);
        } else{
            if(root->left)
                dfs(root->left);
            if(root->right)
                dfs(root->right);
        }
        path.pop_back();
    }

    int sumNumbers(TreeNode* root) {
        dfs(root);
        int sum = 0;
        for(int& num: res)
            sum += num;
        return sum;
    }
};
// @lc code=end
  • 广度优先搜索
  • 构建两个队列，分别存储节点 和 当前节点的“值”
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
31
32
33
34
35
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        vector<int> res;
        int sum = 0;
        if(root==nullptr) return 0;
        queue<TreeNode *> qNode;
        queue<int> qVal;

        qNode.push(root);
        qVal.push(root->val);

        while(!qNode.empty()){
            TreeNode* cur = qNode.front();
            int val = qVal.front();
            qNode.pop(); qVal.pop();

            if(cur->left==nullptr && cur->right==nullptr){
                sum += val;
            } else {
                if(cur->left){
                    int leftVal = val*10 + cur->left->val;
                    qNode.push(cur->left);
                    qVal.push(leftVal);
                }
                if(cur->right){
                    int rightVal = val*10 + cur->right->val;
                    qNode.push(cur->right);
                    qVal.push(rightVal);
                }
            }
        }
        return sum;
    }
};
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！