搜索二叉樹的定義：
它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若它的左子樹不空掺出，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值温眉；
（2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值褒纲。
- 二叉樹中序遍歷的情況下愁溜，遍歷結(jié)果是所有節(jié)點依次升序的，就是搜索二叉樹外厂，否則就不是冕象。
- 由此我們可以對之前非遞歸版本的中序遍歷稍加修改，在打印節(jié)點的時機判斷當(dāng)前節(jié)點是否大于上一個節(jié)點汁蝶，就可以判斷此二叉樹是否是搜索二叉樹渐扮。
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));
}
}
