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.
1 -> 2 -> 3
represents the number 123
.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:
[1, 1000]
.0 <= Node.val <= 9
10
.Given a binary tree where each node contains a digit from 0 to 9, each root-to-leaf path represents a number. Find the total sum of all root-to-leaf numbers. A leaf node is a node with no children.
The most efficient approach is using Depth-First Search (DFS). We traverse the tree recursively, building up the number represented by each path as we go.
Algorithm:
null
, return 0 (no contribution to the sum).Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(H), where H is the height of the tree. This accounts for the recursive call stack. In the worst case (a skewed tree), H could be N, but in a balanced tree, H is log₂N.
Here's the implementation in several programming languages:
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(node, current_sum):
if not node:
return 0
current_sum = current_sum * 10 + node.val
if not node.left and not node.right: # Leaf node
return current_sum
return dfs(node.left, current_sum) + dfs(node.right, current_sum)
return dfs(root, 0)
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode node, int currentSum) {
if (node == null) {
return 0;
}
currentSum = currentSum * 10 + node.val;
if (node.left == null && node.right == null) { // Leaf node
return currentSum;
}
return dfs(node.left, currentSum) + dfs(node.right, currentSum);
}
}
C++:
/**
* 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) {
return dfs(root, 0);
}
int dfs(TreeNode* node, int currentSum) {
if (!node) return 0;
currentSum = currentSum * 10 + node->val;
if (!node->left && !node->right) return currentSum; //Leaf Node
return dfs(node->left, currentSum) + dfs(node->right, currentSum);
}
};
//Other languages (Go, TypeScript, Rust, Javascript, C) are omitted for brevity, but follow the same fundamental recursive DFS pattern. The core logic remains consistent across all languages.