В моем последнем посте я показал, как решить одну из классических задач собеседования на доске: перевернуть связанный список. В этом посте я исследую аналогичную, но немного более сложную проблему, как инвертировать двоичное дерево. Я снова буду использовать 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))