15.二进制搜索树的挑战¶

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

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

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

挑战2：可等式¶

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

挑战3：它是一个子树吗？¶

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

解决方案¶

挑战1的解决方案¶

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

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

在你的Playground页面上写下以下内容：

extension BinaryNode where Element: Comparable {

  var isBinarySearchTree: Bool {
    isBST(self, min: nil, max: nil)
  }

  // 1
  private func isBST(_ tree: BinaryNode<Element>?,
                     min: Element?,
                     max: Element?) -> Bool {
    // 2
    guard let tree = tree else {
      return true
    }

    // 3
    if let min = min, tree.value <= min {
      return false
    } else if let max = max, tree.value > max {
      return false
    }

    // 4
    return isBST(tree.leftChild, min: min, max: tree.value) &&
           isBST(tree.rightChild, min: tree.value, max: max)
  }
}

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

isBST负责递归地遍历树并检查BST属性。它需要通过对BinaryNode的引用来跟踪进度，并跟踪min和max值以验证BST属性。
这是基本情况。如果tree是nil，那么就没有要检查的节点。nil节点是一个二进制搜索树，所以在这种情况下你会返回true。
这本质上是一个边界检查。如果当前值超过了min和max的边界，那么当前节点就违反了二进制搜索树规则。
这一行包含递归调用。当遍历左边的子节点时，当前值被作为max值传入。这是因为左边的任何节点不能大于父节点。反之亦然，当向右遍历时，min值被更新为当前值。右侧的任何节点必须大于父节点。如果任何一个递归调用评估为false，false值将传播回顶部。

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

挑战2的解决方案¶

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

extension BinarySearchTree: Equatable {

  // 1
  public static func ==(lhs: BinarySearchTree,
                        rhs: BinarySearchTree) -> Bool {
    isEqual(lhs.root, rhs.root)
  }

  // 2
  private static func isEqual<Element: Equatable>(
    _ node1: BinaryNode<Element>?,
    _ node2: BinaryNode<Element>?) -> Bool {

  // 3
  guard let leftNode = node1, let rightNode = node2 else {
    return node1 == nil && node2 == nil
  }

  // 4
  return leftNode.value == rightNode.value &&
    isEqual(leftNode.leftChild, rightNode.leftChild) &&
    isEqual(leftNode.rightChild, rightNode.rightChild)
  }
}

下面是对代码的解释：

这是Equatable协议要求的函数。在这个函数里面，你将返回isEqual辅助函数的结果。
isEqual将递归地检查两个节点和它们的后代是否相等。
这是基本情况。如果一个或多个节点是nil，那么就没有必要继续检查。如果两个节点都是nil，它们就是相等的。否则，一个是nil，一个不是nil，所以它们一定不相等。
在这里，你检查左边和右边节点的值是否相等。你也递归地检查左边的孩子和右边的孩子是否相等。

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

挑战3的解决方案¶

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

// 1
extension BinarySearchTree where Element: Hashable {

  public func contains(_ subtree: BinarySearchTree) -> Bool {

    // 2
    var set: Set<Element> = []
    root?.traverseInOrder {
      set.insert($0)
    }

    // 3
    var isEqual = true

    // 4
    subtree.root?.traverseInOrder {
      isEqual = isEqual && set.contains($0)
    }
    return isEqual
  }
}

你将利用一个Set来解决这个问题。要在Set中插入元素，元素必须是Hashable，所以你首先要约束扩展，其中Element是Hashable。
在contains函数中，你首先将当前树中的所有元素插入到集合中。
isEqual是用来存储最终结果的。你需要这个，因为traverseInOrder需要一个闭包，而你不能直接从闭包内返回。
对于子树中的每个元素，你要检查集合是否包含该值。如果在任何时候set.contains($0)评估为false，你将确保isEqual保持false，即使随后的元素评估为true，将isEqual && set.contains($0)分配给自己。

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