判断一个二叉树是否是二叉排序树

二叉排序树也叫做二叉搜索树，是一种常见的二叉树数据结构。它有着以下特点：

1. 每个节点最多有2个子节点。

2. 左子树中所有节点的值都小于该节点的值。

3. 右子树中所有节点的值都大于该节点的值。

4. 没有重复的节点值。

在本文中，我们将从多个角度来分析判断一个二叉树是否是二叉排序树。

角度一：递归法判断二叉树是否是二叉排序树

递归法是最简单的方法之一，具体实现方式如下：

1. 如果当前节点为空，则说明已经遍历到末尾，返回true。

2. 如果当前节点的左子树不为空，则递归检查左子树。

3. 如果当前节点的值小于等于左子树最大节点的值，则说明不是二叉排序树。

4. 如果当前节点的右子树不为空，则递归检查右子树。

5. 如果当前节点的值大于等于右子树最小节点的值，则说明不是二叉排序树。

6. 如果都满足以上条件，则二叉树是二叉排序树。

代码示例：

```java

public boolean isBST(TreeNode root) {

return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

}

private boolean isBST(TreeNode root, long minVal, long maxVal) {

if(root == null) {

return true;

}

if(root.val <= minVal || root.val >= maxVal) {

return false;

}

return isBST(root.left, minVal, root.val) && isBST(root.right, root.val, maxVal);

}

```

角度二：中序遍历法判断二叉树是否是二叉排序树

在中序遍历法中，我们需要先遍历左子树，处理当前节点，再遍历右子树。如果当前节点比上一个节点的值小，则说明不是二叉排序树。

代码示例：

```java

public boolean isBST(TreeNode root) {

Stack stack = new Stack<>();

long preVal = Long.MIN_VALUE;

while(root != null || !stack.isEmpty()) {

while(root != null) {

stack.push(root);

root = root.left;

}

root = stack.pop();

if(root.val <= preVal) {

return false;

}

preVal = root.val;

root = root.right;

}

return true;

}

```

角度三：BST性质判断二叉树是否是二叉排序树

如果我们已经知道该二叉树的所有节点的值，可以直接判断是否满足二叉排序树的性质。

代码示例：

```java

public boolean isBST(int[] nums) {

for(int i=1; i

if(nums[i] <= nums[i-1]) {

return false;

}

}

return true;

}

```