Сложность: 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 {
func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
var stack = [TreeNode]()
var root = root
var k = k
while true {
while root != nil {
stack.append(root!)
root = root?.left
}
root = stack.removeLast()
k -= 1
if k == 0 {
return root!.val
}
root = root?.right
}
}
}Ставь 👍 и забирай 📚 Базу знаний