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

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

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

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

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

Solution：

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
/**
 * 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) {
        int sum = 0;
        if(!root) return 0;
        sumVal(root,0,sum);
        return sum;
    }
    void sumVal(TreeNode* root, int pathsum,int&sum){
        if(!root->left && !root->right){
         sum += pathsum*10 + root->val;  
         return;
        } 
        if(root->left) sumVal(root->left, pathsum*10 + root->val, sum);
        if(root->right) sumVal(root->right, pathsum*10 + root->val, sum);
    }
};

这道题由于是到叶子节点的路径，并且要将其中走过的节点的值加起来，所以不能到空节点才停止（无法确定加值的时机），这里是到叶子节点就停止，并且把值加到sum中。