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