题目来源:https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

标记难度:Medium

提交次数:1/1

代码效率:100.00%

题意

给定一棵二叉树,树上的每个结点都是一个0-9的数位,问所有从根到叶结点的路径代表的数字之和。

分析

这个题和Leetcode 112差不多(我很好奇,为啥那道题就是Easy,这道就变Medium了),主要区别是没有剪枝的必要了,因为是求所有数字的和。题解区里也没看见什么特别惊人的做法。

代码

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
/**
* 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 {
private:
int sum;

void dfs(TreeNode* root, int num) {
if (root == NULL)
return;
num = num * 10 + root->val;
if (root->left == NULL && root->right == NULL) {
sum += num;
return;
}
dfs(root->left, num);
dfs(root->right, num);
}

public:
int sumNumbers(TreeNode* root) {
sum = 0;
dfs(root, 0);
return sum;
}
};