Sum Root to Leaf Numbers

LeetCode
,

第7天，为什么今天随机到了一道水题。。。

今天的题目是129. Sum Root to Leaf Numbers

恩，这是一道打卡水题，明明是道Easy的题目，却混进了Medium中：

这道题有个比较容易想错的方法就是，用后序遍历做：

1
2
3
4
int sumNumbers(TreeNode* root) {
    if (root == nullptr) return 0;
    return sumNumbers(root->left) + sumNumbers(root->right) + 20 * root->val;
}

这个方法对满二叉树是没问题的，但是对于普通的二叉树就会有问题，如：

1
2
3
   1
 /  
2

也就是说，在两边高度不一样时，是会出问题的，为了解决这个问题，我们要把思路换过来，把root到当前节点的值计算出来，并传给子节点去计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return sumNumbers(root, 0);
    }
    int sumNumbers(TreeNode* root, int v) {
        if (root == nullptr) return 0;
        
        v = v*10 + root->val;
        if (root->right == nullptr && root->left == nullptr) return v;
        
        return sumNumbers(root->left, v) + sumNumbers(root->right, v);
    }
};