Сложность: medium
Вам дан корень бинарного дерева поиска (BST), в котором значения ровно двух узлов дерева были поменяны местами по ошибке. Восстановите дерево, не изменяя его структуру.
Пример:
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
👨💻 Алгоритм:
1⃣Создайте симметричный обход дерева. Это должен быть почти отсортированный список, в котором поменяны местами только два элемента.
2⃣Определите два поменянных местами элемента x и y в почти отсортированном массиве за линейное время.
3⃣Повторно пройдите по дереву. Измените значение x на y и значение y на x.
😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
self.val = val
self.left = left
self.right = right
}
}
class Solution {
private var prev: TreeNode?
private var first: TreeNode?
private var second: TreeNode?
private func inorder(_ root: TreeNode?) {
guard let root = root else { return }
inorder(root.left)
if let prev = prev, prev.val > root.val {
if first == nil {
first = prev
}
second = root
}
prev = root
inorder(root.right)
}
func recoverTree(_ root: TreeNode?) {
inorder(root)
if let first = first, let second = second {
swap(&first.val, &second.val)
}
}
}Ставь 👍 и забирай 📚 Базу знаний