Introduction

In this blog post, we will explore how to solve the LeetCode problem "129" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

• Depth-First Search (DFS): Traverse the tree using DFS, maintaining the current number formed along each path.
  • Path Completion: When a leaf node is encountered, add the current number to the total sum.
  • Number Construction: At each node, update the current number by multiplying it by 10 and adding the node's value.

• Time Complexity: O(N), where N is the number of nodes in the tree. Space Complexity: O(H), where H is the height of the tree (call stack depth due to recursion). In the worst case (skewed tree), H = N, and in the best case (balanced tree), H = log N.

Code

    # 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: TreeNode) -> int:
        def dfs(node: TreeNode, current_number: int) -> int:
            if not node:
                return 0

            current_number = current_number * 10 + node.val

            if not node.left and not node.right:
                return current_number

            return dfs(node.left, current_number) + dfs(node.right, current_number)

        return dfs(root, 0)