查找二叉树是否为二叉搜索树
问题内容：
今天，我接受了一次采访，要求我编写一个程序，该程序采用二进制树，如果它也是二进制搜索树，则返回true，否则返回false。
我的方法1：执行有序遍历并将元素存储为O（n）时间。现在浏览元素的数组/列表，检查第 i 个索引处的元素是否大于第（i +
1）个索引处的元素。如果遇到这种情况，则返回false并退出循环。（这需要O（n）时间）。最后返回true。
但是这位先生希望我提供一个有效的解决方案。我尝试了一下，但是没有成功，因为要确定它是否是BST，我必须检查每个节点。
而且他指出我要考虑递归。我的方法2：如果对于任何节点N N-> left为
N，并且N的左节点的有序后继者小于N且有序后继者，则BT是BST。 N的右节点的N大于N，左右子树是BST。
但这将变得很复杂，运行时间似乎并不理想。如果您知道任何最佳解决方案，请提供帮助。
问题答案：
这是一个众所周知的问题，具有以下答案：
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）。
另一种解决方案是进行有序遍历并检查序列是否已排序，特别是因为您已经知道提供了二叉树作为输入。
