129. Sum Root to Leaf Numbers

发表于 | 分类于

每日一题 2019 - 05 - 02

题目：

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

解法：

这个题要求把二叉树路径上的所有数字序列转换成实数并进行求和，直观的思路就是通过存下一个个路径上的数字，随后进行求和即可完成问题，但是直接使用 int 会产生数字大小溢出的情况，所以需要使用unsigned long long int存储求和过程中应有的结果，同时需要记得对每一层使用过的 num 进行还原，避免影响其它层的求解；

代码：

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
/**
 * 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 sumNumbers(TreeNode* root) {
        if(root == NULL)
        {
            return 0 ;
        }   
        vector<unsigned long long int> now ;
        unsigned long long int number = 0 ;
        mysum(number,now,root);
        unsigned long long int max = 0 ;
        for(int i = 0 ; i < now.size() ; i ++ )
        {
            max += now[i];
        }
        return max ;
    }
    void mysum(unsigned long long int &num,vector<unsigned long long int>& now, TreeNode*root)
    {
        if(root == NULL)
        {
            return ;
        }
        num = num * 10 + root -> val ;
        if(root -> left == NULL && root -> right == NULL)
        {
            now.push_back(num);
            num = (num - ( root -> val ) ) / 10 ;
            return ;
        }
        mysum(num,now,root->left);
        mysum(num,now,root->right);
        num = (num - (root -> val)) / 10 ;
    }
};
0%
undefined