12. Сериализация и десериализация двоичного дерева

Вопрос: Создайте функции для сериализации и десериализации бинарного дерева (объект -> строка и строка -> объект).

   20
  / \
 10  15
 /  / \
13  9 8

Первая функция должна возвращать строку, представляющую данное дерево, а вторая должна принимать ту же строку для восстановления исходного дерева.

Подсказки:

- Для просмотра узлов вы можете использовать DFS,

- Вам нужно преобразовать значение узла, но также и нулевой узел,

- Десериализация — это обратная логика сериализации.

Решение:

// 1.
func serializeBinaryTree(binaryNode: BinaryNode<Int>?) -> String {
    // 2.
    guard let binaryNode = binaryNode else { return "" }

    // 3.
    var ouput = ""
    serializeBinaryTree(binaryNode: binaryNode, ouput: &ouput)

    // 4.
    ouput.removeLast()
    return ouput
}

func serializeBinaryTree(binaryNode: BinaryNode<Int>?, ouput: inout String) {
    // 5.
    guard let binaryNode = binaryNode else {
        ouput += "null-"
        return
    }

    // 6.
    ouput += "\(binaryNode.value)-"

    // 7.
    serializeBinaryTree(binaryNode: binaryNode.left, ouput: &ouput)
    serializeBinaryTree(binaryNode: binaryNode.right, ouput: &ouput)
}

// 8.
func deserializeBinaryTree(string: String) -> BinaryNode<Int>? {
    // 9.
    guard !string.isEmpty else { return nil }

    // 10.
    var array = string.components(separatedBy: "-")

    // 11.
    let result = deserializeBinaryTree(array: &array)
    return result
}

private func deserializeBinaryTree(array: inout [String]) -> BinaryNode<Int>? {
    // 12.
    guard !array.isEmpty else { return nil }

    // 13.
    guard let value = Int(array.removeFirst()) else {
        return nil
    }

    // 14.
    let binaryNode = BinaryNode<Int>(value: value)
    binaryNode.left = deserializeBinaryTree(array: &array)
    binaryNode.right = deserializeBinaryTree(array: &array)

    // 15.
    return binaryNode
}

Пояснения:

1. Начнем с сериализации бинарного дерева (объект -> строка).

func serializeBinaryTree(binaryNode: BinaryNode<Int>?) -> String {

2. Если заданный узел равен нулю, вернуть пустую строку.

guard let binaryNode = binaryNode else { return “” }

3. Давайте создадим результирующую пустую строку и вызовем вспомогательный метод с корневым узлом и вновь созданной пустой строкой.

var ouput = “”
serializeBinaryTree(binaryNode: binaryNode, ouput: &ouput)

4. Удалите последний дефис (разделитель узлов), так как он бесполезен, и верните строку.

ouput.removeLast()
return ouput

5. Если данный узел нулевой, добавьте тег «null» и разделитель «-» (это базовый случай для рекурсии).

guard let binaryNode = binaryNode else {
  ouput += "null-"
  return
}

6. В противном случае добавьте значение узла и разделитель «-».

ouput += “\(binaryNode.value)-”

7. Рекурсивно вызывать левый и правый узлы.

serializeBinaryTree(binaryNode: binaryNode.left, ouput: &ouput)
serializeBinaryTree(binaryNode: binaryNode.right, ouput: &ouput)

8. Продолжим десериализацию бинарного дерева (строка -> Объект).

func deserializeBinaryTree(string: String) -> BinaryNode<Int>? {

9. Если строка пуста, вернуть nil.

guard !string.isEmpty else { return nil }

10. Разделим строку по разделителю «-» на массив.

var array = string.components(separatedBy: “-”)

11. Вызовем хелпер метода с только что созданным массивом и вернем полученный узел.

let result = deserializeBinaryTree(array: &array)
return result

12. Если массив пуст, вернуть nil (это базовый случай для рекурсии).

guard !array.isEmpty else { return nil }

13. Возьмем первое значение из массива и удалим его.

guard let value = Int(array.removeFirst()) else {
  return nil
}

14. Создайте новый узел с полученным значением и присвойте результат рекурсии его левому и правому узлу.

let binaryNode = BinaryNode<Int>(value: value)
binaryNode.left = deserializeBinaryTree(array: &array)
binaryNode.right = deserializeBinaryTree(array: &array)

15. В конце концов, верните новый узел.

return binaryNode

Сложность:

- Временная сложность: как для сериализации, так и для десериализации нам нужно будет просмотреть все узлы один раз, тогда временная сложность будет линейной O (n), где n - количество узлов,

- Сложность пространства: размер выходной строки пропорционален размеру дерева, тогда сложность пространства будет линейной O(n), где n - количество узлов.

Тест-кейсы:

public func testSerializeBinaryTree() {
  // 20
  // / \
  // 10 15
  // / / \
  // 13 9 8
  //
  let binaryNode20 = BinaryNode<Int>(value: 20)
  let binaryNode10 = BinaryNode<Int>(value: 10)
  let binaryNode15 = BinaryNode<Int>(value: 15)
  let binaryNode13 = BinaryNode<Int>(value: 13)
  let binaryNode09 = BinaryNode<Int>(value: 09)
  let binaryNode08 = BinaryNode<Int>(value: 08)
  let binaryTree = binaryNode20
  binaryTree.left = binaryNode10
  binaryTree.right = binaryNode15
  binaryNode10.left = binaryNode13
  binaryNode15.left = binaryNode09
  binaryNode15.right = binaryNode08

  let serializedBinaryTree = serializeBinaryTree(binaryNode: binaryTree)
  let newBinaryTree = deserializeBinaryTree(string: serializedBinaryTree)

  assert(binaryTree.value == newBinaryTree?.value, "binaryTree.value not equal")
  assert(binaryTree.left?.value == newBinaryTree?.left?.value, "binaryTree.left?.value not equal")
  assert(binaryTree.right?.value == newBinaryTree?.right?.value, "binaryTree.right?.value not equal")
  assert(binaryTree.left?.left?.value == newBinaryTree?.left?.left?.value, "binaryTree.left?.left?.value not equal")
  assert(binaryTree.left?.right?.value == newBinaryTree?.left?.right?.value, "binaryTree.left?.right?.value not equal")
  assert(binaryTree.right?.left?.value == newBinaryTree?.right?.left?.value, "binaryTree.right?.left?.value not equal")
  assert(binaryTree.right?.right?.value == newBinaryTree?.right?.right?.value, "binaryTree.right?.right?.value not equal")
}

Следовать за:

Нет дополнительного вопроса.

‹‹ Структуры данных, алгоритмы и вопросы для интервью ››

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:

• 👏 Хлопайте за историю и подписывайтесь на автора 👉
• 📰 Смотрите больше контента в публикации Level Up Coding
• 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"

🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу