你如何验证二叉搜索树？ [英] How do you validate a binary search tree?

问题描述

我在被称为验证二叉搜索树的采访阅读这里的锻炼。

I read on here of an exercise in interviews known as validating a binary search tree.

究竟是如何工作的呢？什么会之一的验证二叉搜索树找？我写了一个基本的搜索树，但从来没有听说过这个概念。

How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, but never heard of this concept.

推荐答案

其实这是错误的每个人都在做的专访。

Actually that is the mistake everybody does in an interview.

Leftchild必须依据它来检查（minLimitof节点，node.value）

Leftchild must be checked against (minLimitof node,node.value)

Rightchild必须对被检查（node.value，MAXLIMIT节点）

Rightchild must be checked against (node.value,MaxLimit of node)

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

另一种解决方案（如果空间不是约束）： 做树的序遍历并存储在数组中的节点值。如果数组是有序，它是一种有效的BST否则不是。

Another solution (if space is not a constraint): Do an inorder traversal of the tree and store the node values in an array. If the array is in sorted order, its a valid BST otherwise not.

这篇关于你如何验证二叉搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！