第15章：二进制搜索树进阶

你认为你已经掌握了二进制搜索树的窍门？试试这三个挑战，把概念锁定下来。

挑战1：二叉树还是二叉搜索树？

创建一个函数，检查二叉树是否是二叉搜索树。

挑战2：等式

二叉搜索树目前缺乏Equatable的一致性。您的挑战是采用Equatable协议。

挑战 3：是否是子树？

创建一个方法，检查当前树是否包含另一个树的所有元素。你可以要求元素是Hashable。

解决方案

挑战1的解决方案

二元搜索树是指每个左子都小于或等于其父，每个右子都大于其父的树。

验证一棵树是否是二进制搜索树的算法包括遍历所有节点并检查这一属性。

在你的playground页面上写下以下内容。

isBinarySearchTree 是将被暴露出来供外部使用的接口。同时，神奇的事情发生在 isBST 函数中。

  1. isBST 负责递归地遍历树并检查 BST 属性。它需要通过对二进制节点的引用来跟踪进度，同时也要跟踪最小和最大值以验证BST属性。

  2. 这是基本情况。如果树是nil，那么就没有要检查的节点。一个nil节点是一个二进制搜索树，所以在这种情况下你会返回true。

  3. 这本质上是一个边界检查。如果当前值超过了min和max的边界，那么当前节点就违反了二进制搜索树规则。

  4. 这一行包含递归调用。当遍历左边的子节点时，当前值被作为最大值传入。这是因为左边的任何节点不能大于父节点。反之亦然，当向右遍历时，最小值被更新为当前值。右侧的任何节点必须大于父节点。如果任何一个递归调用的结果是错误的，错误的值就会传播到顶部。

这个解决方案的时间复杂度是O(n)，因为你需要遍历整个树一次。还有一个O(n)空间成本，因为你要进行n次递归调用。

挑战2的解决方案

符合Equatable是比较简单的。要使两棵二叉树相等，两棵树必须有相同的元素，且顺序相同。下面是解决方案的样子。

下面是对代码的解释。

  1. 这是Equatable协议要求的函数。在这个函数里面，你将返回isEqual辅助函数的结果。

  2. isEqual将递归地检查两个节点和它们的后代是否相等。

  3. 这是基本情况。如果一个或多个节点是nil，那么就没有必要继续检查。如果两个节点都是nil，它们就是相等的。否则，一个是nil，一个不是nil，所以它们一定不相等。

  4. 在这里，你检查左、右节点的值是否相等。你还递归地检查左边的孩子和右边的孩子是否相等。

这个函数的时间复杂度是O(n)。这个函数的空间复杂度是O(n)。

挑战3的解决方案

你的目标是创建一个方法，检查当前树是否包含另一棵树的所有元素。换句话说，当前树中的值必须是另一棵树的值的超集。下面是解决方案的样子。

  1. 在这个解决方案中，你将使用一个Set。要向Set中插入元素，元素必须是Hashable的，所以你首先要约束Element是Hashable的扩展。

  2. 在contains函数中，你首先将当前树中的所有元素插入到集合中。

  3. isEqual是用来存储最终结果的。你需要这个，因为traverseInOrder需要一个闭包，而你不能直接从闭包内返回。

  4. 对于子树中的每个元素，你要检查集合是否包含该值。如果在任何时候set.contains($0)的值是假的.

    你将确保isEqual一直是假的，即使后面的元素的值是真的，你将isEqual && set.contains($0)分配给自己。

这个算法的时间复杂度是O(n)。这个算法的空间复杂度是O(n)。

上一章 目录 下一章