二叉搜索树(也叫二叉排序树、二叉查找树,Binary Search Tree),或是空树,或是满足以下性质的二叉树:
- 若左子树不空,则左子树所有节点的值均小于其根节点值
- 其右子树不空,则右子树所有节点的值均大于其根节点值
- 左右子树也分别是一颗二叉搜索树
由二叉搜索树性质,当对其进行中序遍历时,结果是递增序列。所有可以通过中序遍历的思想判断是否为一颗二叉搜索树。
public class IsBST {
//静态全局变量,保存中序遍历中上一个节点的值
public static int preValue = Integer.MIN_VALUE;
//递归中序遍历判断是否是二叉搜索树
public static boolean isBST(Node<Integer> head) {
if (head == null) {
return true;
}
boolean isLeftBst = isBST(head.left);
if (!isLeftBst) {
return false;
}
if (head.value <= preValue) {
return false;
} else {
preValue = head.value;
}
return isBST(head.right);
}
//非递归中序遍历判断是否为二叉搜索树
public static boolean isBST2(Node<Integer> head) {
if (head != null) {
int preValue = 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 <= preValue) {
return false;
} else {
preValue = head.value;
}
head = head.right;
}
}
}
return true;
}
//方法三 树型DP(树型动态规划)
public static boolean isBST3(Node<Integer> head) {
return process(head).isBST;
}
public static class ReturnData {
public boolean isBST;
public int min;
public int max;
public ReturnData(boolean isBST, int min, int max) {
this.isBST = isBST;
this.min = min;
this.max = max;
}
}
public static ReturnData process(Node<Integer> x) {
if (x == null) {
return null;
}
ReturnData leftData = process(x.left);
ReturnData rightData = process(x.right);
int min = x.value;
int max = x.value;
if (leftData != null) {
min = Math.min(min, leftData.min);
max = Math.max(max, leftData.max);
}
if (rightData != null) {
min = Math.min(min, rightData.min);
max = Math.max(max, rightData.max);
}
boolean isBST = true;
if (leftData != null && (!leftData.isBST || leftData.max >= x.value)) {
isBST = false;
}
if (rightData != null && (!rightData.isBST || rightData.min <= x.value)) {
isBST = false;
}
return new ReturnData(isBST, min, max);
}
}