搜索二叉树的定义：
它或者是一棵空树，或者是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
- 二叉树中序遍历的情况下，遍历结果是所有节点依次升序的，就是搜索二叉树，否则就不是。
- 由此我们可以对之前非递归版本的中序遍历稍加修改，在打印节点的时机判断当前节点是否大于上一个节点，就可以判断此二叉树是否是搜索二叉树。
public class IsBST {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isBST(Node head) {
if (head == null) {
return true;
}
int pre = Integer.MIN_VALUE;
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if (head.value < pre) {
return false;
}
pre = head.value;
head = head.right;
}
}
return true;
}
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(2);
head.right = new Node(6);
head.left.left = new Node(1);
head.left.right = new Node(3);
head.right.left = new Node(5);
System.out.println(isBST(head));
}
}
