Given a binary tree containing digits from 0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1 / \ 2 3
The root-to-leaf path 1->2
represents the number 12
.
The root-to-leaf path 1->3
represents the number 13
.
Return the sum = 12 + 13 = 25
.
Subscribe to see which companies asked this question
class Solution { public: int sumNumbers(TreeNode* root) { return dfs(root, 0); } int dfs(TreeNode* root, int sum){ if (root == 0) return 0; if (root->left == NULL && root->right == NULL) { return sum * 10 + root->val; } return dfs(root->left, sum * 10 + root->val) + dfs(root->right, sum * 10 + root->val); } };
#include#include #include using namespace std; //Definition for binary tree struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: int sumNumbers(TreeNode* root) { return dfs(root, 0); } int dfs(TreeNode* root, int sum){ if (root == 0) return 0; if (root->left == NULL && root->right == NULL) { return sum * 10 + root->val; } return dfs(root->left, sum * 10 + root->val) + dfs(root->right, sum * 10 + root->val); } }; void createTree(TreeNode *&root) { int i; cin >> i; if (i != 0) { root = new TreeNode(i); if (root == NULL) return; createTree(root->left); createTree(root->right); } } int main() { Solution s; TreeNode *root; createTree(root); int path = s.sumNumbers(root); cout << path <