Сложность: medium
Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки.
Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.
Пример:
Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]
👨💻 Алгоритм:
1⃣Инициализация: Проход по дереву и добавление всех узлов в очередь, чтобы отслеживать узлы, у которых есть хотя бы одно пустое место для нового дочернего узла.
2⃣Вставка: Добавление нового узла в первое доступное место слева направо.
3⃣Возвращение корня: Просто возвращает корневой узел.
😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}
class CBTInserter {
private var root: TreeNode
private var deque = [TreeNode]()
init(_ root: TreeNode) {
self.root = root
var queue = [TreeNode]()
queue.append(root)
while !queue.isEmpty {
let node = queue.removeFirst()
if node.left == nil || node.right == nil {
deque.append(node)
}
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
}
func insert(_ v: Int) -> Int {
let node = deque[0]
let newNode = TreeNode(v)
if node.left == nil {
node.left = newNode
} else {
node.right = newNode
deque.removeFirst()
}
deque.append(newNode)
return node.val
}
func get_root() -> TreeNode {
return root
}
}Ставь 👍 и забирай 📚 Базу знаний