给定一棵二叉树的根节点，判断其是否为二叉搜索树。
二叉搜索树：每一棵子树的根节点，左子树的值比根节点的值小，右子树的值比根节点的值大。
经典的二叉搜索树是没有重复值的。如果要放重复值，那么一定是在一个节点中用某种数据结构存放着，而不是产生多个值重复的节点。
判断一棵树是否为搜索二叉树的方法：
方法一：中序遍历整棵树，如果该中序遍历的序列是升序的，则是搜索二叉树，否则不是。
方法二：用递归套路解决：
①目标：假设以 X 节点为根的二叉树是否为搜索二叉树；
②可能性：通过向左树获得某些信息，向右树获得某些信息的情况下来列举可能性；
③ X 是搜索二叉树的原则：
（1）X左树是搜索二叉树；
（2）X右树是搜索二叉树；
（3）X左树的最大值 < X节点的值；
（4）X节点的值 < X 右树的最小值；
所以对于每一个子树的根节点，只需要上面 4 个信息就能支持判断该子树是否为搜索二叉树。
整理可得，需要向左树获得信息：1. 是否为搜索二叉树；2. 最大值。
向右树获得信息：1. 是否为搜索二叉树；2. 最小值。
此时发现向左树和右树需要获得的信息不一样，怎么办呢？求全集！！
即是说，向左树和右树都需要获得信息包括（1）是否为搜索二叉树；（2）最大值；（3）最小值。
递归对所有的节点一视同仁，不要定制任何节点的信息。
/*************************************************************************
> File Name: 035.判断二叉树是否为二叉搜索树.cpp
> Author: Maureen
> Mail: Maureen@qq.com
> Created Time: 五 7/ 1 15:56:01 2022
************************************************************************/
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
class TreeNode {
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int data) : value(data) {}
};
//方法一: 中序遍历
void inOrder(TreeNode *node, vector<int> &arr) {
if (node == nullptr) return ;
inOrder(node->left, arr);
arr.push_back(node->value);
inOrder(node->right, arr);
}
bool process1(TreeNode *root) {
vector<int> ans;
inOrder(root, ans);
for (int i = 1; i < ans.size(); i++) {
if (ans[i - 1] > ans[i])
return false;
}
return true;
}
bool isBST1(TreeNode *root) {
if (root == nullptr) return true;
return process1(root);
}
//方法二：二叉树的递归套路
class Info {
public:
bool isBST;
int maxVal;
int minVal;
Info(bool i, int ma, int mi) : isBST(i), maxVal(ma), minVal(mi) {}
};
Info *process2(TreeNode *root) {
if (root == nullptr) {
return nullptr;
}
//获取左树信息
Info *leftInfo = process2(root->left);
//获取右树信息
Info *rightInfo = process2(root->right);
//设置最值
int maxVal = root->value;
int minVal = root->value;
//左树不为空, 更新最值
if (leftInfo != nullptr) {
maxVal = max(maxVal, leftInfo->maxVal);
minVal = min(minVal, leftInfo->minVal);
}
//右树不为空，更新最值
if (rightInfo != nullptr) {
maxVal = max(maxVal, rightInfo->maxVal);
minVal = min(minVal, rightInfo->minVal);
}
bool isBST = true;
//左树不为空，且左树的最大值 >= 根节点的值
if (leftInfo != nullptr && (!leftInfo->isBST || leftInfo->maxVal >= root->value) ) {
isBST = false;
}
//右树不为空，且右树的最小值 <= 根节点的值
if (rightInfo != nullptr && (!rightInfo->isBST || rightInfo->minVal <= root->value) ) {
isBST = false;
}
return new Info(isBST, maxVal, minVal);
}
bool isBST2(TreeNode *root) {
if (root == nullptr) return true;
return process2(root)->isBST;
}
//for test
TreeNode *generate(int level, int maxlevel, int maxval) {
if (level > maxlevel || (rand() % 100 / 101) < 0.5)
return nullptr;
TreeNode *root = new TreeNode(rand() % maxval);
root->left = generate(level + 1, maxlevel, maxval);
root->right = generate(level + 1, maxlevel, maxval);
return root;
}
TreeNode *generateRandomBST(int maxlevel, int maxval) {
return generate(1, maxlevel, maxval);
}
int main() {
srand(time(0));
int level = 4;
int value = 100;
int testTime = 1000001;
for (int i = 0; i < testTime; i++) {
TreeNode *root = generateRandomBST(level, value);
if (isBST1(root) != isBST2(root)) {
cout << "Failed!" << endl;
return 0;
}
}
cout << "Success!" << endl;
return 0;
}
import java.util.ArrayList;
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 isBST1(Node head) {
if (head == null) {
return true;
}
ArrayList<Node> arr = new ArrayList<>();
in(head, arr);
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i).value <= arr.get(i - 1).value) {
return false;
}
}
return true;
}
public static void in(Node head, ArrayList<Node> arr) {
if (head == null) {
return;
}
in(head.left, arr);
arr.add(head);
in(head.right, arr);
}
//方法二：使用递归套路
public static boolean isBST2(Node head) {
if (head == null) return true;
return process2(head).isBST;
}
public static class Info {
boolean isBST; //是否为搜索二叉树
public int min; //最小值
public int max; //最大值
public Info(boolean is, int mi, int ma) {
isBST = is;
min = mi;
max = ma;
}
}
//自己实现了这些信息，才能在递归中从左右子树中获取相同的信息
public static Info process2(Node x) {
//空树不好设置min和max，于是直接返回空，让上游调用者处理
if (x == null) {
return null;
}
//向左树获取信息
Info leftInfo = process2(x.left);
//向右树获取信息
Info rightInfo = process2(x.right);
//将获取的信息填充到Info中，就能知道当前x节点是否为搜索二叉树
int min = x.value;
int max = x.value;
if (leftInfo != null) {
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
}
boolean isBST = true;
//左树不为空，但是左树不是搜索二叉树
if (leftInfo != null && !leftInfo.isBST) {
isBST = false;
}
//右树不为空，但是左树不是搜索二叉树
if (rightInfo != null && !rightInfo.isBST) {
isBST = false;
}
//左树不为空，但是左树的最大值>=x节点的值
if (leftInfo != null && leftInfo.max >= x.value) {
isBST = false;
}
//右树不为空，但是右树的最小值<=x节点的值
if (rightInfo != null && rightInfo.min <= x.value) {
isBST = false;
}
return new Info(isBST, min, max);
}
//对数器
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static void main(String[] args) {
int maxLevel = 4;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isBST1(head) != isBST2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}