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.
Examples:
Example 1:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.Solution in Python:
To solve the problem of summing all root-to-leaf numbers in a binary tree, we need to traverse the tree and compute the number represented by each path from the root to the leaf nodes. We can use Depth-First Search (DFS) to achieve this.
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:
# Helper function to perform DFS on the tree
def dfs(node, current_number):
if not node:
return 0
# Update the current number by appending the current node's value
current_number = current_number * 10 + node.val
# If it's a leaf node, return the current number
if not node.left and not node.right:
return current_number
# Recursively call dfs for left and right children and sum the results
left_sum = dfs(node.left, current_number)
right_sum = dfs(node.right, current_number)
return left_sum + right_sum
# Initialize the dfs with the root node and 0 as the initial number
return dfs(root, 0)Explanation
- TreeNode Class:
- This class defines the structure of a tree node, which contains a value
val, and pointers to left and right children.
- This class defines the structure of a tree node, which contains a value
- Solution Class and sumNumbers Method:
- The
sumNumbersmethod is defined within theSolutionclass, which takes the root of the binary tree as an input and returns the total sum of all root-to-leaf numbers.
- The
- dfs Function:
- This is a helper function to perform the depth-first search.
- It takes two arguments:
node(the current node) andcurrent_number(the number formed from the root to the current node). - If the current node is
None, it returns 0 (base case for recursion). - The
current_numberis updated by appending the current node’s value (i.e., multiplyingcurrent_numberby 10 and adding the node’s value). - If the current node is a leaf node (no left and right children), it returns the
current_number. - Otherwise, it recursively calls
dfsfor the left and right children and sums the results.
- Starting the DFS:
- The DFS is initiated by calling
dfs(root, 0)whererootis the root of the tree and0is the initial value forcurrent_number.
- The DFS is initiated by calling
This solution ensures that all root-to-leaf paths are considered, and their corresponding numbers are correctly summed up. The constraints guarantee that the recursion will not run into deep recursion issues, making this approach efficient and suitable for the problem’s requirements.
Solution in Javascript:
JavaScript
// Definition for a binary tree node.
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
// Helper function to perform DFS on the tree
function dfs(node, currentNumber) {
if (node === null) {
return 0;
}
// Update the current number by appending the current node's value
currentNumber = currentNumber * 10 + node.val;
// If it's a leaf node, return the current number
if (node.left === null && node.right === null) {
return currentNumber;
}
// Recursively call dfs for left and right children and sum the results
let leftSum = dfs(node.left, currentNumber);
let rightSum = dfs(node.right, currentNumber);
return leftSum + rightSum;
}
// Initialize the dfs with the root node and 0 as the initial number
return dfs(root, 0);
};Solution in Java:
Java
class Solution {
public int sumNumbers(TreeNode root) {
// Helper function to perform DFS on the tree
return dfs(root, 0);
}
private int dfs(TreeNode node, int currentNumber) {
if (node == null) {
return 0;
}
// Update the current number by appending the current node's value
currentNumber = currentNumber * 10 + node.val;
// If it's a leaf node, return the current number
if (node.left == null && node.right == null) {
return currentNumber;
}
// Recursively call dfs for left and right children and sum the results
int leftSum = dfs(node.left, currentNumber);
int rightSum = dfs(node.right, currentNumber);
return leftSum + rightSum;
}
}Solution in C#:
C#
public class Solution {
public int SumNumbers(TreeNode root) {
// Start the DFS traversal with the root node and initial number as 0
return DFS(root, 0);
}
private int DFS(TreeNode node, int currentNumber) {
if (node == null) {
// Base case: if the current node is null, return 0
return 0;
}
// Update the current number by appending the current node's value
currentNumber = currentNumber * 10 + node.val;
// If it's a leaf node, return the current number
if (node.left == null && node.right == null) {
return currentNumber;
}
// Recursively call DFS for left and right children and sum the results
int leftSum = DFS(node.left, currentNumber);
int rightSum = DFS(node.right, currentNumber);
return leftSum + rightSum;
}
}