Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

3⃣Обработка запросов:
Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса.

😎 Решение:

class Solution {
    fun calcEquation(equations: List<List<String>>, values: List<Double>, queries: List<List<String>>): DoubleArray {
        val graph = mutableMapOf<String, MutableMap<String, Double>>()

        for ((i, equation) in equations.withIndex()) {
            val A = equation[0]
            val B = equation[1]
            val value = values[i]
            graph.computeIfAbsent(A) { mutableMapOf() }[B] = value
            graph.computeIfAbsent(B) { mutableMapOf() }[A] = 1.0 / value
        }

        fun bfs(start: String, end: String): Double {
            if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
            val queue = ArrayDeque<Pair<String, Double>>()
            queue.add(start to 1.0)
            val visited = mutableSetOf<String>()

            while (queue.isNotEmpty()) {
                val (current, curProduct) = queue.removeFirst()
                if (current == end) return curProduct
                visited.add(current)
                for ((neighbor, value) in graph[current] ?: emptyMap()) {
                    if (neighbor !in visited) {
                        queue.add(neighbor to curProduct * value)
                    }
                }
            }
            return -1.0
        }

        return queries.map { bfs(it[0], it[1]) }.toDoubleArray()
    }
}

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

Задача: 296. Best Meeting Point
Сложность: hard

Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия.

Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи.

Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

1⃣Определение координат домов:
Пройдите по сетке и соберите координаты всех домов (ячейки с значением 1) в два списка: один для координат x и один для координат y.

2⃣Нахождение медианы:
Отсортируйте списки координат x и y.
Найдите медианы в обоих списках. Медианы координат x и y укажут оптимальную точку встречи.

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

😎 Решение:

class Solution {
    fun minTotalDistance(grid: Array<IntArray>): Int {
        var minDistance = Int.MAX_VALUE
        for (row in grid.indices) {
            for (col in grid[0].indices) {
                val distance = search(grid, row, col)
                minDistance = minOf(distance, minDistance)
            }
        }
        return minDistance
    }

    private fun search(grid: Array<IntArray>, row: Int, col: Int): Int {
        val q: ArrayDeque<Triple<Int, Int, Int>> = ArrayDeque()
        q.add(Triple(row, col, 0))
        val m = grid.size
        val n = grid[0].size
        val visited = Array(m) { BooleanArray(n) }
        var totalDistance = 0

        while (q.isNotEmpty()) {
            val (r, c, d) = q.removeFirst()

            if (r < 0 || c < 0 || r >= m || c >= n || visited[r][c]) {
                continue
            }

            if (grid[r][c] == 1) {
                totalDistance += d
            }

            visited[r][c] = true

            q.add(Triple(r + 1, c, d + 1))
            q.add(Triple(r - 1, c, d + 1))
            q.add(Triple(r, c + 1, d + 1))
            q.add(Triple(r, c - 1, d + 1))
        }

        return totalDistance
    }
}

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

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.

Пример:

Input: n = 10, pick = 6
Output: 6

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

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного.

3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного.

😎 Решение:

class Solution : GuessGame() {
    fun guessNumber(n: Int): Int {
        var low = 1
        var high = n
        while (low <= high) {
            val mid = low + (high - low) / 2
            val res = guess(mid)
            if (res == 0)
                return mid
            else if (res < 0)
                high = mid - 1
            else
                low = mid + 1
        }
        return -1
    }
}

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

Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

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

1⃣Определите количество возможных двоичных кодов длины k.

2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:

class Solution {
    fun hasAllCodes(s: String, k: Int): Boolean {
        val need = 1 shl k
        val got = BooleanArray(need)
        val allOne = need - 1
        var hashVal = 0
        
        for (i in s.indices) {
            hashVal = ((hashVal shl 1) and allOne) or (s[i] - '0')
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true
                if (got.all { it }) {
                    return true
                }
            }
        }
        return false
    }
}

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

Гарантируется, что каждый город может добраться до города 0 после перенаправления.

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    var count = 0

    fun dfs(node: Int, parent: Int, adj: Map<Int, List<Pair<Int, Int>>>) {
        adj[node]?.forEach { (neighbor, sign) ->
            if (neighbor != parent) {
                count += sign
                dfs(neighbor, node, adj)
            }
        }
    }

    fun minReorder(n: Int, connections: Array<IntArray>): Int {
        val adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
        for (connection in connections) {
            adj.computeIfAbsent(connection[0]) { mutableListOf() }.add(connection[1] to 1)
            adj.computeIfAbsent(connection[1]) { mutableListOf() }.add(connection[0] to 0)
        }
        dfs(0, -1, adj)
        return count
    }
}

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

class CombinationIterator(characters: String, combinationLength: Int) {
    private val combinations: MutableList<String> = mutableListOf()

    init {
        val n = characters.length
        val k = combinationLength
        for (bitmask in 0 until (1 shl n)) {
            if (bitmask.countOneBits() == k) {
                val curr = StringBuilder()
                for (j in 0 until n) {
                    if (bitmask and (1 shl (n - j - 1)) != 0) {
                        curr.append(characters[j])
                    }
                }
                combinations.add(curr.toString())
            }
        }
    }

    fun next(): String {
        return combinations.removeAt(combinations.size - 1)
    }

    fun hasNext(): Boolean {
        return combinations.isNotEmpty()
    }
}

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST), где левое поддерево содержит только узлы с ключами меньше текущего, а правое — только с ключами больше текущего. Оба поддерева также должны быть BST.

Пример:

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

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

1⃣Используем симметричный обход дерева (inorder), при котором значения должны идти строго по возрастанию.

2⃣Храним значение предыдущего узла и сравниваем его с текущим: если текущее значение не больше предыдущего — дерево не BST.

3⃣Таким образом, проходим дерево один раз, не храня весь список обхода, что экономит память.

😎 Решение:

class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Solution {
    private var prev: Long = Long.MIN_VALUE

    private fun inorder(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        if (!inorder(root.left)) {
            return false
        }
        if (root.value <= prev) {
            return false
        }
        prev = root.value.toLong()
        return inorder(root.right)
    }

    fun isValidBST(root: TreeNode?): Boolean {
        return inorder(root)
    }
}

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

fun reachTarget(target: Int): Int {
    var target = kotlin.math.abs(target)
    var position = 0
    var steps = 0
    while (position < target || (position - target) % 2 != 0) {
        steps++
        position += steps
    }
    return steps
}

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

1⃣Установите два указателя — с начала и конца строки.

2⃣Пропускайте неалфавитно-цифровые символы, сравнивая символы, пока указатели не сойдутся.

3⃣Если встретились несовпадающие символы — это не палиндром, иначе — да.

😎 Решение:

class Solution {
    fun isPalindrome(s: String): Boolean {
        var i = 0
        var j = s.length - 1

        while (i < j) {
            while (i < j && !s[i].isLetterOrDigit()) {
                i++
            }
            while (i < j && !s[j].isLetterOrDigit()) {
                j--
            }

            if (s[i].toLowerCase() != s[j].toLowerCase()) {
                return false
            }

            i++
            j--
        }

        return true
    }
}

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

1⃣Инициализация нового массива с такими же значениями, как у исходного массива.
Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться.

2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей.
Если элемент меньше своего левого и правого соседей, увеличиваем его.
Если элемент больше своего левого и правого соседей, уменьшаем его.

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

class Solution {
    fun transformArray(arr: IntArray): IntArray {
        var arr = arr
        var changed: Boolean
        do {
            changed = false
            val newArr = arr.copyOf()
            for (i in 1 until arr.size - 1) {
                if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                    newArr[i]++
                    changed = true
                } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                    newArr[i]--
                    changed = true
                }
            }
            arr = newArr
        } while (changed)
        return arr
    }
}

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

Задача: 250. Count Univalue Subtrees
Сложность: medium

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

Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.

Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

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

1⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3⃣Верните count.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private var count = 0

    private fun dfs(node: TreeNode?): Boolean {
        if (node == null) {
            return true
        }

        val isLeftUniValue = dfs(node.left)
        val isRightUniValue = dfs(node.right)

        if (isLeftUniValue && isRightUniValue) {
            if (node.left != null && node.left!!.`val` != node.`val`) {
                return false
            }
            if (node.right != null && node.right!!.`val` != node.`val`) {
                return false
            }
            count++
            return true
        }
        return false
    }

    fun countUnivalSubtrees(root: TreeNode?): Int {
        dfs(root)
        return count
    }
}

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

Задача: 36. Valid Sudoku
Сложность: medium

Определите, является ли доска Судоку 9x9 валидной. Проверяются только заполненные ячейки, следуя правилам:
- В каждой строке числа 1-9 не повторяются.
- В каждом столбце числа 1-9 не повторяются.
- В каждом 3x3 блоке числа 1-9 не повторяются.

Пример:

Input: board =  
[["5","3",".",".","7",".",".",".","."]  
,["6",".",".","1","9","5",".",".","."]  
,[".","9","8",".",".",".",".","6","."]  
,["8",".",".",".","6",".",".",".","3"]  
,["4",".",".","8",".","3",".",".","1"]  
,["7",".",".",".","2",".",".",".","6"]  
,[".","6",".",".",".",".","2","8","."]  
,[".",".",".","4","1","9",".",".","5"]  
,[".",".",".",".","8",".",".","7","9"]]  
Output: true  

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

1⃣Создаем три массива Set, чтобы отслеживать числа в строках, столбцах и 3x3 блоках.

2⃣Проходим по каждой ячейке, проверяя наличие дубликатов в соответствующих множествах.

3⃣Если не найдено повторений, возвращаем true, иначе false.

😎 Решение:

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        val N = 9
        val rows = Array(N) { mutableSetOf<Char>() }
        val cols = Array(N) { mutableSetOf<Char>() }
        val boxes = Array(N) { mutableSetOf<Char>() }

        for (r in 0 until N) {
            for (c in 0 until N) {
                val value = board[r][c]
                if (value == '.') continue

                if (!rows[r].add(value) || !cols[c].add(value) || !boxes[(r / 3) * 3 + (c / 3)].add(value)) {
                    return false
                }
            }
        }

        return true
    }
}

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium

Дан бинарный массив nums, из которого следует удалить один элемент.

Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует.

Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

1⃣Инициализация переменных:
zeroCount для подсчёта нулей в текущем окне, longestWindow для хранения максимальной длины окна, содержащего не более одного нуля, и start для левой границы окна.

2⃣Итерация по массиву:
При каждом элементе увеличиваем zeroCount, если это ноль.
Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.
Обновляем longestWindow текущей длиной окна i - start.

3⃣Возврат результата:
Вернуть longestWindow.

😎 Решение:

class Solution {
    fun longestSubarray(nums: IntArray): Int {
        var zeroCount = 0
        var longestWindow = 0
        var start = 0

        for (i in nums.indices) {
            if (nums[i] == 0) {
                zeroCount++
            }

            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--
                }
                start++
            }

            longestWindow = maxOf(longestWindow, i - start)
        }

        return longestWindow
    }
}

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

Задача: 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)
    }
}

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