В моем последнем посте я показал, как решить одну из классических задач собеседования на доске: перевернуть связанный список. В этом посте я исследую аналогичную, но немного более сложную проблему, как инвертировать двоичное дерево. Я снова буду использовать Swift 3 для написания кода.

Бинарное дерево можно рассматривать как серию узлов, каждый из которых имеет значение, а также до двух дочерних узлов. Мы будем называть детей левой и правой ветвью.

Листовой узел - это особый узел, который имеет только значение. Он отмечает конец дерева.

Мы также определим пустой узел, который не содержит значения и ветвей. Мы будем использовать это, чтобы указать, когда у узла отсутствует ветвь. Таким образом, нам не нужно делать ветвь необязательным значением.

Вот как наше двоичное дерево будет выглядеть в Swift.

public enum BinaryTree<T> {
    case empty
    case leaf(value: T)
    indirect case node(
        value: T, left: BinaryTree<T>, right: BinaryTree<T>)
}

Это должно быть похоже на то, как мы определили структуру данных связанного списка.

Теперь можно написать функцию для инвертирования двоичного дерева. Чтобы инвертировать дерево, мы собираемся поменять местами левую и правую ветви каждого узла в дереве. Это эффективно превратит дерево в его зеркальное отображение.

public func inverted() -> BinaryTree<T> {
    switch self {
    case .empty:
        return .empty
    case .leaf(let value):
        return .leaf(value: value)
    case .node(let value, let left, let right):
        return .node(value: value,
                     left: right.inverted(),
                     right: left.inverted())
    }
}

Это прямое рекурсивное преобразование, как и обращение связанного списка.

Теперь осталось только продемонстрировать нашу новую функцию в действии.

Поскольку визуализировать дерево может быть немного сложно, мы создадим настраиваемое свойство описания, которое будет рекурсивно спускаться по дереву и создавать представление его значений.

extension BinaryTree: CustomStringConvertible {
    public var description: String {
        switch self {
        case .empty:
            return "()"
        case .leaf(let value):
            return "\(value)"
        case .node(let value, let left, let right):
            return "(\(left) <- \(value) -> \(right))"
        }
    }
}

Чтобы применить метод инвертирования, давайте построим дерево с числами от 1 до 6, добавленными в отсортированном порядке. После инвертирования дерева мы должны обнаружить, что значения теперь расположены в порядке убывания!

let tree: BinaryTree<Int> = .node(
    value: 4,
    left: .node(
        value: 2,
        left: .leaf(value: 1),
        right:.leaf(value: 3)),
    right: .node(
        value: 6,
        left: .leaf(value: 5),
        right: .empty))
print(tree)
// ((1 <- 2 -> 3) <- 4 -> (5 <- 6 -> ()))
print(tree.inverted())
// ((() <- 6 -> 5) <- 4 -> (3 <- 2 -> 1))