129. Sum Root to Leaf Numbers

[mah-shamim]

Topics: Tree, Depth-First Search, Binary Tree

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 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 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.

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.

[topugit]

We can use a Depth-First Search (DFS) approach. The idea is to traverse the tree, keeping track of the number formed by the path from the root to the current node. When you reach a leaf node, you add the current number to the total sum.

Let's implement this solution in PHP: 129. Sum Root to Leaf Numbers

<?php
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function sumNumbers($root) {
    return sumNumbersRecu($root, 0);
}

function sumNumbersRecu($node, $currentSum) {
    if ($node === null) {
        return 0;
    }

    // Update the current sum with the value of the current node
    $currentSum = $currentSum * 10 + $node->val;

    // If the node is a leaf, return the current sum
    if ($node->left === null && $node->right === null) {
        return $currentSum;
    }

    // Recursively call dfs for left and right children
    return sumNumbersRecu($node->left, $currentSum) + sumNumbersRecu($node->right, $currentSum);
}

// Example usage:

// Example 1
$root1 = new TreeNode(1);
$root1->left = new TreeNode(2);
$root1->right = new TreeNode(3);
echo sumNumbers($root1); // Output: 25

// Example 2
$root2 = new TreeNode(4);
$root2->left = new TreeNode(9);
$root2->right = new TreeNode(0);
$root2->left->left = new TreeNode(5);
$root2->left->right = new TreeNode(1);
echo sumNumbers($root2); // Output: 1026

?>

Explanation:

1. TreeNode Class: This class represents each node of the binary tree. Each node has a value (val), a left child (left), and a right child (right).

2. sumNumbers Function: This is the main function that initiates the DFS traversal by calling the sumNumbersRecu function with the root node and an initial currentSum of 0.

3. sumNumbersRecu Function:

• Base Case: If the node is null, return 0 (this handles the case where there is no child node).
• Update Current Sum: For each node, update the currentSum by multiplying the previous currentSum by 10 and adding the node's value.
• Leaf Node Check: If the node is a leaf (i.e., it has no left or right child), return the currentSum as this represents the number formed by the path from the root to this leaf.
• Recursive Calls: If the node is not a leaf, recursively call sumNumbersRecu on both the left and right children and return their sum.

Edge Cases:

• The function handles cases where the tree has only one node.
• It correctly computes the sum even for deeper trees, as the depth of the tree will not exceed 10 (as per the problem constraints).

This solution runs efficiently with a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

[mah-shamim]

thanks to solve the "Sum Root to Leaf Numbers" problem

[topugit]

thanks