判断是否是二叉搜索树

判断一棵树是否是二叉搜索树。

二叉搜索树：二叉树的一个节点的值都比它的左子树的所有节点的值都大，它的右子树的所有节点的值都比它大，它的子树也满足这些条件。

public static boolean isBST(Node head) {
	if (head == null) {
		return true;
	}
	boolean res = true;
	Node pre = null;
	Node cur1 = head;
	Node cur2 = null;
	while (cur1 != null) {
		cur2 = cur1.left;
		if (cur2 != null) {
			while (cur2.right != null && cur2.right != cur1) {
				cur2 = cur2.right;
			}
			if (cur2.right == null) {
				cur2.right = cur1;
				cur1 = cur1.left;
				continue;
			} else {
				cur2.right = null;
			}
		}
		if (pre != null && pre.value > cur1.value) {
			res = false;
		}
		pre = cur1;
		cur1 = cur1.right;
	}
	return res;
}

完全二叉树：
定义：一个节点的左右孩子有以下四种情况：

• 1，左右双全
• 2，有左没右
• 3，没左有右
• 4，左右都没有
  如果情况3，则直接返回false。
  如果是1、4情况，则后面的所有节点都是叶节点才是完全二叉树，否则返回false。

public static boolean isCBT(Node head) {
	if (head == null) {
		return true;
	}
	Queue<Node> queue = new LinkedList<Node>();
	boolean leaf = false;
	Node l = null;
	Node r = null;
	queue.offer(head);
	while (!queue.isEmpty()) {
		head = queue.poll();
		l = head.left;
		r = head.right;
		if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
			return false;
		}
		if (l != null) {
			queue.offer(l);
		}
		if (r != null) {
			queue.offer(r);
		} else {
			leaf = true;
		}
	}
	return true;
}