Задача: 129. Sum Root to Leaf Numbers
Сложность: Medium

Вам дан корень бинарного дерева, содержащего только цифры от 0 до 9.

Каждый путь от корня до листа в дереве представляет собой число.

Например, путь от корня до листа 1 -> 2 -> 3 представляет число 123.
Верните общую сумму всех чисел от корня до листа. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Листовой узел — это узел без детей.

Пример:

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.

👨‍💻 Алгоритм:

1⃣Инициализация:
Создайте переменные для хранения суммы чисел (rootToLeaf) и текущего числа (currNumber), а также стек для обхода дерева, начиная с корневого узла.

2⃣Обход дерева:
Используйте стек для глубинного обхода дерева (DFS), обновляя currNumber путём умножения на 10 и добавления значения узла. Для каждого листа добавляйте currNumber к rootToLeaf.

3⃣Возвращение результата:
По завершении обхода всех узлов возвращайте rootToLeaf, содержащую сумму всех чисел от корня до листьев дерева.

😎 Решение:

class Solution {
    func sumNumbers(_ root: TreeNode?) -> Int {
        var rootToLeaf = 0, currNumber = 0
        var stack: [(TreeNode?, Int)] = []
        stack.append((root, 0))
        
        while !stack.isEmpty {
            let p = stack.removeLast()
            let node = p.0
            currNumber = p.1
            
            if let root = node {
                currNumber = currNumber * 10 + root.val
              
                if root.left == nil && root.right == nil {
                    rootToLeaf += currNumber
                } else {
                    if let right = root.right {
                        stack.append((right, currNumber))
                    }
                    if let left = root.left {
                        stack.append((left, currNumber))
                    }
                }
            }
        }
        return rootToLeaf
    }
}

Ставь 👍 и забирай 📚 Базу знаний