查找二叉树是否为二叉搜索树

Question

今天我接受采访时,我被要求编写一个程序,该程序采用二叉树,如果它也是二进制搜索树则返回true,否则为false.

我的方法1:执行有序遍历并将元素存储在O(n)时间内.现在扫描数组/元素列表并检查^第 i ^个索引处的元素是否大于^第(i + 1)^个索引处的元素.如果遇到这种情况,则返回false并退出循环.(这需要O(n)时间).最后回归真实.

但这位先生希望我提供一个有效的解决方案.我尝试但是我没有成功,因为要查找它是否是BST我必须检查每个节点.

而且他指着我思考递归.我的方法2:如果对于任何节点N N>左<N和N>右> N,并且N的左节点的有序后继小于N并且有序后继,则BT是BST N的右节点大于N,左右子树是BST.

但这会很复杂,而且运行时间似乎并不好.如果您知道任何最佳解决方案,请帮忙.

Answer 1

这是一个非常着名的问题,有以下答案:

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

递归调用确保子树节点在其祖先的范围内,这很重要.运行时复杂度将为O(n),因为每个节点都被检查一次.

另一种解决方案是进行顺序遍历并检查序列是否已排序,尤其是因为您已经知道二进制树是作为输入提供的.

Answer 2

@Dhruv提供的答案很好.除此之外,这是另一种在O(n)时间内工作的解决方案.
我们需要在这种方法中跟踪前一个节点.在每次递归调用中,我们使用当前节点数据检查先前的节点数据.如果当前节点数据小于先前,则返回false

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}