blob: 7c02f90651bf19a6e03e3db6c4a748d242c57466 (
plain)
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
|
// 129. Sum Root to Leaf Numbers
#include "leetcode.h"
/*
* given 'root' of binary tree containing digits 0-9 only. each root-to-leaf
* pattern in the tree represents a number. eg. root-to-leaf path 1->2->3
* represents the integer 123. return total sum of all root-to-leaf numbers.
* test cases will fit in 32-bit integer. a leaf node is a node with no children
*/
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode *createNode(int val) {
struct TreeNode *new_node =
(struct TreeNode *)malloc(sizeof(struct TreeNode));
new_node->val = val;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
int calc_num(struct TreeNode *root, int tree_num) {
if (!root)
return 0;
return !root->left && !root->right
? tree_num * 10 + root->val
: calc_num(root->left, tree_num * 10 + root->val) +
calc_num(root->right, tree_num * 10 + root->val);
}
int sumNumbers(struct TreeNode *root) { return calc_num(root, 0); }
int main() {
struct TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
printf("%d\n", sumNumbers(root)); // expect: 25
}
|