Сложность: medium
Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.
Пример:
Input: root = [3,1,4,null,2], k = 1
Output: 1
👨💻 Алгоритм:
1⃣Инициализация стека и обход в глубину: Инициализируйте стек для хранения узлов дерева. Начните обход дерева в глубину, начиная с корня, и перемещайтесь влево, добавляя каждый узел в стек, пока не достигнете самого левого узла.
2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.
3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение.
😎 Решение:
class Solution {
kthSmallest(root, k) {
let stack = []
while (true) {
while (root !== null) {
stack.push(root)
root = root.left
}
root = stack.pop()
if (--k === 0) return root.val
root = root.right
}
}
}Ставь 👍 и забирай 📚 Базу знаний