🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 897. Increasing Order Search Tree
Сложность: easy
Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.
Пример:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
👨💻 Алгоритм:
1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.
2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.
3⃣Вернуть новый корень дерева (первый элемент списка).
😎 Решение:
class TreeNode(var `val`: Int = 0) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun increasingBST(root: TreeNode?): TreeNode? {
val nodes = mutableListOf()
fun inorder(node: TreeNode?) {
if (node == null) return
inorder(node.left)
nodes.add(node)
inorder(node.right)
}
inorder(root)
for (i in 0 until nodes.size - 1) {
nodes[i].left = null
nodes[i].right = nodes[i + 1]
}
nodes.last().left = null
nodes.last().right = null
return nodes.first()
Ставь 👍 и забирай 📚 Базу знаний
