使用广度优先搜索和顺序遍历来分析一个非常大的二叉搜索树的有效性

Question

我在考虑检查二叉搜索树有效性的不同技术。当然，需要保持的不变性是左子树必须小于或等于当前节点，而当前节点又应该小于或等于右子树。有几种不同的方法可以解决这个问题：第一种是检查每个子树上值的约束，可以像这样概述（在 Java 中，对于整数节点）：

public static boolean isBST(TreeNode node, int lower, int higher){
   if(node == null) return true;
   else if(node.data < lower || node.data > higher) return false;
   return isBST(node.left, lower, node.data) && isBST(node.right, node.data, higher);
}

还有另一种使用 inOrder 遍历来实现此目的的方法，您可以在其中跟踪前一个元素并确保进度严格不递减。不过，这两种方法都首先探索左子树，如果我们在根的右子树中间不一致，推荐的路径是什么？我知道可以使用BFS变体，但是是否可以同时使用多种技术，是否建议这样做？例如，我们可以对 BFS、inorder 和 reverse Inorder 进行，并在检测到故障时返回。这也许只适用于非常大的树，以便以更多的空间和访问相同数据结构的多个线程为代价来减少平均运行时间。当然，如果我们使用一个简单的迭代解来求解（不是修改树的莫里斯遍历），我们将耗尽 O（lgN） 空间。

Answer 1

我希望这取决于您的确切情况。特别是，树失败为二进制的概率是多少，以及失败发生的预期深度。

例如，如果树可能是正确的二进制，那么使用 3 种多种技术将是浪费，因为有效树的整体运行时间将大约增加三倍。

Answer 2

迭代深化深度优先搜索怎么样？

它通常（渐近地）与广度优先搜索一样快（并且还会发现任何早期故障），但使用的内存与深度优先搜索一样少。

它通常看起来像这样：

boolean isBST(TreeNode node, int lower, int higher, int depth)
{
  if (depth == 0)
    return true;
  ...
  isBST(..., depth-1)
  ...
}

访客：

boolean failed = false;
int treeHeight = height(root);
for (int depth = 2; depth <= treeHeight && !failed; depth++)
  failed = !isBST(root, -INFINITY, INFINITY, depth);