Swift | LeetCode

Задача: 988. Smallest String Starting From Leaf Сложность: medium Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'. Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня. Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей. Например, "ab" лексикографически меньше, чем "aba". Лист узла - это узел, у которого нет потомков. Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:

class Solution {
    var ans = "~"
    
    func smallestFromLeaf(_ root: TreeNode?) -> String {
        dfs(root, "")
        return ans
    }
    
    func dfs(_ node: TreeNode?, _ path: String) {
        guard let node = node else { return }
        let currentPath = String(UnicodeScalar(node.val + 97)!) + path
        if node.left == nil && node.right == nil {
            ans = min(ans, currentPath)
        }
        dfs(node.left, currentPath)
        dfs(node.right, currentPath)
    }
}

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