Задача: 513. Find Bottom Left Tree Value
Сложность: medium

Дан корень двоичного дерева, верните самое левое значение в последней строке дерева.

Пример:

Input: root = [2,1,3]
Output: 1

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

1⃣Инициализируйте переменную maxDepth для хранения глубины нижнего уровня дерева. Инициализируйте переменную bottomLeftValue для хранения самого левого значения в последней строке дерева.

2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    private var maxDepth = -1
    private var bottomLeftValue = 0
    
    fun findBottomLeftValue(root: TreeNode?): Int {
        dfs(root, 0)
        return bottomLeftValue
    }
    
    private fun dfs(current: TreeNode?, depth: Int) {
        if (current == null) return
        
        if (depth > maxDepth) {
            maxDepth = depth
            bottomLeftValue = current.`val`
        }
        
        dfs(current.left, depth + 1)
        dfs(current.right, depth + 1)
    }
}

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

Задача: 269. Alien Dictionary
Сложность: hard

Существует новый инопланетный язык, использующий английский алфавит, но в неизвестном порядке.
Дан массив слов words, отсортированных лексикографически по правилам этого языка.
Найти возможный порядок букв. Если такого порядка не существует — верните пустую букву.

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

1⃣Извлечение отношений порядка и создание списков смежности:
Извлечь отношения порядка между буквами из слов.
Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого.

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import java.util.*

class Solution {
    fun alienOrder(words: Array<String>): String {
        val adjList = mutableMapOf<Char, MutableSet<Char>>()
        val inDegree = mutableMapOf<Char, Int>()

        for (word in words) {
            for (char in word) {
                inDegree[char] = 0
            }
        }

        for ((firstWord, secondWord) in words.zip(words.drop(1))) {
            for ((c, d) in firstWord.zip(secondWord)) {
                if (c != d) {
                    if (d !in adjList.getOrDefault(c, mutableSetOf())) {
                        adjList.getOrPut(c) { mutableSetOf() }.add(d)
                        inDegree[d] = inDegree.getOrDefault(d, 0) + 1
                    }
                    break
                }
            }
            if (secondWord.length < firstWord.length && firstWord.startsWith(secondWord)) {
                return ""
            }
        }

        val output = mutableListOf<Char>()
        val queue: Queue<Char> = LinkedList()

        for ((char, degree) in inDegree) {
            if (degree == 0) {
                queue.add(char)
            }
        }

        while (queue.isNotEmpty()) {
            val c = queue.poll()
            output.add(c)
            for (d in adjList.getOrDefault(c, emptySet())) {
                inDegree[d] = inDegree[d]!! - 1
                if (inDegree[d] == 0) {
                    queue.add(d)
                }
            }
        }

        if (output.size < inDegree.size) {
            return ""
        }

        return output.joinToString("")
    }
}

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!