输入一个二叉树的 root 节点，判断是否是二叉搜索树。

1
public boolean isBST(TreeNode root)

二叉搜索树的定义：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。

根据这个定义，比如有个函数 f(root) 用作判断是否是 BST，那么这个函数进一步可以定义为 f(root, min, max)，min 和 max 表示遍历过程中的最大值和最小值。在当前状态下，root.val > min 且 root.val < max 就是合法的。同样的，对于 root.left 和 root.right 也需要满足上述条件。写成的伪代码就是

1
2
3
4
5
f(root, min, max) {
if root.val < min return false
if root.val > max return false
return f(root.left, min, root.val) && f (root.right, root.val, max)
}

通过 inOrder(中序遍历) 是另一种巧妙的方法，基于二叉搜索树的定义可以明确知道中序遍历的过程一定是节点值从小到大的，因此可以认为 只要没有满足递增的序列，就不是合法的二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// min, max 法
boolean isValidBST(TreeNode root, TreeNode lower, TreeNode upper) {
    if (root == null) return true;
    if (lower != null && lower.val >= root.val) return false;
    if (upper != null && upper.val <= root.val) return false;
    return isValidBST(root.left, lower, root) && isValidBST(root.right, root, upper);
}

// 中序遍历法
public boolean isValidBST(TreeNode root) {
  ArrayList<Integer> order = new ArrayList<>();
  inOrder(root, order);
  for (int i = 1; i < order.size(); i++) {
    if (order.get(i) <= order.get(i - 1)) return false;
  }
  return true;
}

private void inOrder(TreeNode root, ArrayList<Integer> order) {
  if (root == null) return;
  inOrder(root.left, order);
  order.add(root.val);
  inOrder(root.right, order);
}