找到不是 BST 的最小高度的根

Question

我正在努力解决以下问题：

编写函数，对于给定的二叉树 returns 当树是 BST 时，最小高度的根不是 BST 或 NIL。

我知道如何检查树是否是 BST 但不知道如何重写它。如果有伪代码算法，我将不胜感激。

Answer 1

我不想直接跳到此处适用的算法，而是给出一系列观察结果，最终得出一个非常好的算法来解决这个问题。

首先，假设对于树中的每个节点，您知道以该节点为根的子树中的最大值和最小值。（我们将它们表示为 min(x) 和 max(x)，其中 x 是树中的一个节点）。鉴于此信息，我们可以进行以下观察：

Observation 1: A node x is the root of a non-BST if x ≤ max(x.left) or if x ≥ min(y.right)

这不是一个当且仅当条件 - 它只是一个 "if" - 但它是一个有用的观察结果。这样做的原因是，如果 x ≤ max(x.left)，则 x 的左子树中有一个节点不小于 x，这意味着以 x 为根的树不是 BST，如果 x > min(x.right)，则x的右子树中有一个节点不大于x，说明以x为根的树不是BST。

现在，x < min(x.right) 和 x > max(x.left) 的任何节点不一定是 BST 的根。考虑这棵树，例如：

这里，根节点比它的左子树的所有东西都大，比它的右子树的所有东西都小，但是整棵树本身并不是二叉搜索树。这是因为以 1 和 6 为根的树不是 BST。这导致了一个有用的观察：

Observation 2: If x > max(x.left) and x < min(x.right), then x is a BST if and only if x.left and x.right are BSTs.

此结果证明的快速草图：如果 x.left 和 x.right 是 BST，则对树进行中序遍历将列出 x.left 中的所有值按升序排列，然后是 x，然后 x.right 中的所有值按升序排列。由于 x > max(x.left) 和 x < min(x.right)，这些值是排序的，因此树是 BST。另一方面，如果 x.left 或 x.right 不是 BST，那么这些值返回的顺序将不会排序，因此树不是 BST。

这两个属性提供了一种非常好的方法来查找树中不是 BST 根的每个节点。思路是从叶子向上遍历树中的节点，检查每个节点的值是否大于其左子树的max且小于其右子树的min，然后检查其左右子树是否为BST .您可以使用后序遍历来执行此操作，如下所示：

 /* Does a postorder traversal of the tree, tagging each node with its
  * subtree min, subtree max, and whether the node is the root of a
  * BST.
  */
 function findNonBSTs(r) {
     /* Edge case for an empty tree. */
     if (r is null) return;

     /* Process children - this is a postorder traversal. This also
      * tags each child with information about its min and max values
      * and whether it's a BST.
      */
     findNonBSTs(r.left);
     findNonBSTs(r.right);

     /* If either subtree isn't a BST, we're done. */
     if ((r.left  != null && !r.left.isBST) ||
         (r.right != null && !r.right.isBST)) {
        r.isBST = false;
        return;
     }

     /* Otherwise, both children are BSTs. Check against the min and
      * max values of those subtrees to make sure we're in range.
      */
     if ((r.left  != null && r.left.max  >= r.value) ||
         (r.right != null && r.right.min <= r.value)) {
        r.isBST = false;
        return;
     }

     /* Otherwise, we're a BST, and our min and max value can be
      * computed from the left and right children.
      */
     r.isBST = true;
     r.min = (r.left  != null? r.left.min  : r.value);
     r.max = (r.right != null? r.right.max : r.value);
}

你已经运行通过这棵树，每个节点都将被标记为是否是二叉搜索树。从那里开始，您所要做的就是再次遍历树以找到不是 BST 的最深节点。我将把它留作 reader 的众所周知的练习。 :-)

希望对您有所帮助！

找到不是 BST 的最小高度的根

Find root of minimal height which is not BST

algorithm

tree

binary-tree

binary-search-tree

data-structures