blob: d1bc9c6a5d378cbc3d74aa3967833500400b1478 (
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
*/
class Solution {
public:
int sumNumbers(TreeNode *root) {
int sum = 0, curr = 0, depth = 0;
while (root) {
if (root->left) {
auto pre = root->left;
depth = 1;
while (pre->right && pre->right != root) {
pre = pre->right;
depth++;
}
if (!pre->right) {
pre->right = root;
curr = curr * 10 + root->val;
root = root->left;
} else {
pre->right = nullptr;
if (!pre->left)
sum += curr;
curr /= pow(10, depth);
}
} else {
curr = curr * 10 + root->val;
if (!root->right)
sum += curr;
root = root->right;
}
}
return sum;
}
};
|