第13章：二叉树进阶

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

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

挑战1：树的高度

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

挑战2：序列化

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

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

为了澄清这个问题，请考虑以下二进制树。

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

解决方案

挑战1的解决方案

寻找二叉树高度的递归方法非常简单。

  1. 这是递归解决方案的基本情况。如果节点为nil，你将返回-1。

  2. 这里，你递归调用高度函数。每访问一个节点，你就给最高的子节点的高度加一。

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

挑战2的解决方案

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

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

遍历

在你的playground页面中写下以下代码。

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

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

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

序列化

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

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

序列化将返回一个新的数组，该数组包含树的值，并以预排序。

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

反序列化

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

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

下面是代码的工作原理。

  1. 解序列化函数接收一个向外的数值数组。这很重要，因为你可以在每个递归步骤中对数组进行突变，并允许未来的递归调用看到这些变化。

  2. 这是基本情况。如果 removeFirst 返回 nil，则数组中没有更多的元素；因此，你将在这里结束递归。

  3. 你通过从当前值创建一个节点并递归调用deserialize来分配节点给左边和右边的子节点来重新组装树。请注意，这与前序遍历非常相似，只是你建立节点而不是提取它们的值。

你的算法现在已经准备好进行测试了! 在你的playground底部写下以下内容。

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

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

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

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

在你之前创建的反序列化函数之后编写以下函数。

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

这是一个辅助函数，在调用主反序列化函数之前首先反转了数组。在另一个反序列化函数中，找到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)。

上一章 目录 下一章