Сложность: 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, содержащее лексикографически наименьший путь от листа до корня.
😎 Решение:
public class Solution {
private String ans = "~";
public String smallestFromLeaf(TreeNode root) {
dfs(root, new StringBuilder());
return ans;
}
private void dfs(TreeNode node, StringBuilder path) {
if (node == null) return;
path.append((char) (node.val + 'a'));
if (node.left == null && node.right == null) {
path.reverse();
String s = path.toString();
path.reverse();
if (s.compareTo(ans) < 0) {
ans = s;
}
}
dfs(node.left, path);
dfs(node.right, path);
path.deleteCharAt(path.length() - 1);
}
}Ставь 👍 и забирай 📚 Базу знаний