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

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

---

C代码：二叉树

// 之前考虑的是用一个数组保存字符串的顺序，判断是字符串后再换算成int类型，再加到sum上！
// 上面的方法有点多此一举了，直接dfs向下层传递sum

int dfs(struct TreeNode* root, int prevSum) {
    if (root == NULL) {
        return 0;
    }
    int sum = prevSum * 10 + root->val;
    if (root->left == NULL && root->right == NULL) {  // 前序判断，到叶子节点后就返回值；
        return sum;
    }
    int leftSum = dfs(root->left, sum);
    int rightSum = dfs(root->right, sum);
    return leftSum + rightSum;            // 后序处理：直接把叶子节点的sum累加起来，往上层传递
}

int sumNumbers(struct 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