Sum Root to Leaf Numbers 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 -> 3
represents 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.
Example 1:


Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path1->2
represents the number12
. The root-to-leaf path1->3
represents the number13
. Therefore, sum = 12 + 13 =25
.
Example 2:


Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path4->9->5
represents the number 495. The root-to-leaf path4->9->1
represents the number 491. The root-to-leaf path4->0
represents the number 40. Therefore, sum = 495 + 491 + 40 =1026
.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]
. 0 <= Node.val <= 9
- The depth of the tree will not exceed
10
.
Sum Root to Leaf Numbers Solutions
✅Time: O(n)
✅Space: O(h)
C++
class Solution {
public:
int sumNumbers(TreeNode* root) {
int ans = 0;
dfs(root, 0, ans);
return ans;
}
private:
void dfs(TreeNode* root, int path, int& ans) {
if (!root)
return;
if (!root->left && !root->right) {
ans += path * 10 + root->val;
return;
}
dfs(root->left, path * 10 + root->val, ans);
dfs(root->right, path * 10 + root->val, ans);
}
};
Java
class Solution {
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return ans;
}
private int ans = 0;
private void dfs(TreeNode root, int path) {
if (root == null)
return;
if (root.left == null && root.right == null) {
ans += path * 10 + root.val;
return;
}
dfs(root.left, path * 10 + root.val);
dfs(root.right, path * 10 + root.val);
}
}
Python
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(root: Optional[TreeNode], path: int) -> None:
nonlocal ans
if not root:
return
if not root.left and not root.right:
ans += path * 10 + root.val
return
dfs(root.left, path * 10 + root.val)
dfs(root.right, path * 10 + root.val)
dfs(root, 0)
return ans
Watch Tutorial
Checkout more Solutions here