Description
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
- For example, the root-to-leaf path
1 -> 2 -> 3represents the number123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Solution
This problem is about finding all paths of a tree. Recall that a leaf (end of a path) in a tree is a node without any children.
To solve this problem, we do traverse all the nodes in the tree and only add the number generated when reaching a leaf node.
Implementation
As I don’t want to use recursion:
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode* root) {
int output = 0;
TreeNode* node = nullptr;
int sum = 0;
stack<pair<TreeNode*, int>> temp;
temp.push({root, 0});
while (!temp.empty()) {
auto tup = temp.top();
node = tup.first;
sum = tup.second;
temp.pop();
if (!node->left && !node->right) output += sum * 10 + node->val;
if (node->left) temp.push({node->left, sum * 10 + node->val});
if (node->right) temp.push({node->right, sum * 10 + node->val});
}
return output;
}
};
Recursive version:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void runner(TreeNode* root, int sum, int &output) {
if (!root->left && !root->right) output += sum * 10 + root->val;
if (root->left) runner(root->left, (sum * 10 + root->val), output);
if (root->right) runner(root->right, (sum * 10 + root->val), output);
}
int sumNumbers(TreeNode* root) {
int output = 0;
runner(root, 0, output);
return output;
}
};