给定一棵二叉树的根节点，判断其是否为二叉搜索树。
2、分析二叉搜索树：每一棵子树的根节点，左子树的值比根节点的值小，右子树的值比根节点的值大。
经典的二叉搜索树是没有重复值的。如果要放重复值，那么一定是在一个节点中用某种数据结构存放着，而不是产生多个值重复的节点。
判断一棵树是否为搜索二叉树的方法：
-
方法一：中序遍历整棵树，如果该中序遍历的序列是升序的，则是搜索二叉树，否则不是。
-
方法二：用递归套路解决：
①目标：假设以 X 节点为根的二叉树是否为搜索二叉树；
②可能性：通过向左树获得某些信息，向右树获得某些信息的情况下来列举可能性；
③ X 是搜索二叉树的原则：
（1）X左树是搜索二叉树；
（2）X右树是搜索二叉树；
（3）X左树的最大值 < X节点的值；
（4）X节点的值 < X 右树的最小值；所以对于每一个子树的根节点，只需要上面 4 个信息就能支持判断该子树是否为搜索二叉树。
整理可得，需要向左树获得信息：1. 是否为搜索二叉树；2. 最大值。
向右树获得信息：1. 是否为搜索二叉树；2. 最小值。
此时发现向左树和右树需要获得的信息不一样，怎么办呢？求全集！！
即是说，向左树和右树都需要获得信息包括（1）是否为搜索二叉树；（2）最大值；（3）最小值。
递归对所有的节点一视同仁，不要定制任何节点的信息。
#includeJava 版#include #include using namespace std; class TreeNode { public: int value; TreeNode *left; TreeNode *right; TreeNode(int data) : value(data) {} }; //方法一: 中序遍历 void inOrder(TreeNode *node, vector &arr) { if (node == nullptr) return ; inOrder(node->left, arr); arr.push_back(node->value); inOrder(node->right, arr); } bool process1(TreeNode *root) { vector 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 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 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!");
}
}
