13.二叉树的挑战¶

二叉树是算法面试中一个令人惊讶的热门话题。关于二叉树的问题不仅要求你对遍历的工作原理有良好的基础，而且还可以测试你对递归回溯的理解，所以测试一下你在前一章学到的东西是很好的。

打开启动器项目，开始这些挑战。

挑战1：树的高度¶

给出一棵二叉树，找出树的高度。根和最远的叶子之间的距离决定了树的高度。只有一个节点的二叉树的高度为零，因为这个节点既是根又是最远的叶子。

挑战2：序列化¶

软件开发中的一项常见任务是将一个对象序列化为另一种数据类型。这个过程被称为序列化，在只支持封闭的数据类型的系统中允许自定义类型。

串行化的一个例子是JSON。你的任务是设计一种方法，将二进制树序列化为一个数组，并将数组反序列化为相同的二进制树。

为了说明这个问题，请考虑以下二进制树：

一个特定的算法可能会输出序列化为[15, 10, 5, nil, nil, 12, nil, nil, 25, 17, nil, nil]。反序列化过程应该将数组转回相同的二进制树。注意，有很多方法可以进行序列化。你可以选择任何你希望的方式。

解决方案¶

挑战1的解决方案¶

寻找二叉树高度的递归方法很简单：

func height<T>(of node: BinaryNode<T>?) -> Int {

  // 1
  guard let node = node else {
    return -1
  }

  // 2
  return 1 + max(height(of: node.leftChild), height(of: node.rightChild))
}

这是递归解决方案的基本情况。如果节点是nil，你将返回-1。
这里，你递归地调用高度函数。每访问一个节点，你就在最高的子节点的高度上加一。

这个算法的时间复杂度为O(n)，因为你需要遍历所有的节点。这个算法的空间成本为O(n)，因为你需要对调用栈进行同样的n次递归调用。

挑战2的解决方案¶

对二叉树进行序列化或反序列化的方法有很多。遇到这个问题时，你的首要任务是决定遍历的策略。

在这个解决方案中，你将探讨如何通过选择前顺序的遍历策略来解决这个难题。

遍历¶

在你的Playground页面中写下以下代码：

extension BinaryNode {

  public func traversePreOrder(visit: (Element?) -> Void) {
    visit(value)
    if let leftChild = leftChild {
      leftChild.traversePreOrder(visit: visit)
    } else {
      visit(nil)
    }
    if let rightChild = rightChild {
      rightChild.traversePreOrder(visit: visit)
    } else {
      visit(nil)
    }
  }
}

这个函数实现了前顺序的遍历。如代码所示，前序遍历将遍历每个节点，在遍历子节点之前访问该节点。

需要指出的是，你需要访问nil节点，因为为序列化和反序列化记录这些节点是必不可少的。

和所有的遍历函数一样，这个算法对每个树元素都进行一次遍历，所以它的时间复杂度为O(n)。

串行化¶

对于序列化，你只需简单地遍历树并将值存储到一个数组中。数组中的元素有T?类型，因为你需要跟踪nil节点。在你的Playground页面中写下以下内容：

func serialize<T>(_ node: BinaryNode<T>) -> [T?] {
  var array: [T?] = []
  node.traversePreOrder { array.append($0) }
  return array
}

serialize将返回一个新的数组，其中包含树的值，并以预排序。

序列化步骤的时间复杂度是O(n)。因为你要创建一个新的数组，这也会产生一个O(n)的空间成本。

反序列化¶

在序列化过程中，你执行了一个预排序遍历，并将这些值组装成一个数组。反序列化过程是将数组中的每个值重新组装到树中。

你的目标是遍历数组，并以预排序的格式重新组装树。在你的Playground页面的底部写下以下内容：

// 1
func deserialize<T>(_ array: inout [T?])
  -> BinaryNode<T>? {

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

  // 3
  let node = BinaryNode(value: value)
  node.leftChild = deserialize(&array)
  node.rightChild = deserialize(&array)
  return node
}

以下是代码的工作方式：

解序列化函数接收一个inout数组的值。这很重要，因为你可以在每个递归步骤中对数组进行突变，并允许未来的递归调用看到这些变化。
这是基本情况。如果removeFirst返回nil，则数组中没有更多的元素；因此，你将在这里结束递归。
你通过从当前值创建一个节点并递归调用deserialize来分配节点给左边和右边的子节点来重新组装树。注意，这与前序遍历非常相似，只是你建立节点而不是提取它们的值。

你的算法现在可以进行测试了! 在你的Playground底部写下以下内容：

var array = serialize(tree)
let node = deserialize(&array)
print(node!)

你应该在你的控制台看到以下内容：

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

你的反序列化的树反映了所提供的Playground中的样本树。这是你想要的行为。

然而，正如前面所提到的，这个函数的时间复杂性并不理想。因为你调用removeFirst的次数与数组中的元素一样多，这个算法的时间复杂度是O(n²)。幸运的是，有一个简单的方法来弥补这个缺陷。

在你之前创建的deserialize函数之后编写以下函数：

func deserialize<T>(_ array: [T?]) -> BinaryNode<T>? {
  var reversed = Array(array.reversed())
  return deserialize(&reversed)
}

这是一个辅助函数，在调用主deserialize函数之前，首先将数组反转。在另一个deserialize函数中，找到removeFirst函数的调用，并将其改为以下内容：

guard !array.isEmpty, let value = array.removeLast() else {
  return nil
}

这个微小的变化对性能有很大影响。removeFirst是一个O(n)的操作，因为在每次移除后，被移除的元素之后的每个元素都必须向左移动以占据缺失的空间。相比之下，removeLast是一个O(1)操作。

最后，找到并更新deserialize的调用位置，以使用新的辅助函数来反转数组：

let node = deserialize(&array) // old

let node = deserialize(array) // new

你应该看到反序列化过程前后的相同树。这个解决方案的时间复杂度现在是O(n)。因为你创建了一个新的反转数组并选择了一个递归解决方案，这个算法的空间复杂度为O(n)。