Description:
https://leetcode.com/problems/sum-root-to-leaf-numbers/#/description
Algorithm:
Just recursion, not difficult.
Code:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {};
};
class binaryTree {
public:
TreeNode *root;
vector<int> treeElement;
int N;
public:
binaryTree(vector<int> treeElementInput) {
treeElement = treeElementInput;
N = treeElement.size();
root = new TreeNode(treeElement[0]);
makeNode(root, 0);
}
void makeNode(TreeNode *node, int index)
{
if (2 * index + 1 < N)
{
if (treeElement[2 * index + 1] != NULL)
{
TreeNode *T_left = new TreeNode(treeElement[2 * index + 1]);
node->left = T_left;
makeNode(node->left, 2 * index + 1);
}
else
{
node->left = NULL;
}
}
if (2 * index + 2 < N)
{
if (treeElement[2 * index + 2] != NULL)
{
TreeNode *T_right = new TreeNode(treeElement[2 * index + 2]);
node->right = T_right;
makeNode(node->right, 2 * index + 2);
}
else
{
node->right = NULL;
}
}
}
void printTreeNodes(TreeNode *node)
{
if (node != NULL)
{
cout << node->val << endl;
printTreeNodes(node->left);
printTreeNodes(node->right);
}
}
};
class Solution {
public:
int sumNumbers(TreeNode* root) {
if (!root)
return 0;
return helper(root, 0);
}
int helper(TreeNode* node, int sum)
{
if (!node)
return 0;
if (node->left == nullptr && node->right == nullptr) // leaf
return sum + node->val;
else if (node->left == nullptr && node->right != nullptr)
{
return helper(node->right, (sum + node->val) * 10);
}
else if (node->left != nullptr && node->right == nullptr)
{
return helper(node->left, (sum + node->val) * 10);
}
else
{
return helper(node->right, (sum + node->val) * 10) + helper(node->left, (sum + node->val) * 10);
}
}
};