判断二叉树是否为二叉搜索树

1、题目

给定一棵二叉树的根节点，判断其是否为二叉搜索树。

2、分析

二叉搜索树：每一棵子树的根节点，左子树的值比根节点的值小，右子树的值比根节点的值大。

经典的二叉搜索树是没有重复值的。如果要放重复值，那么一定是在一个节点中用某种数据结构存放着，而不是产生多个值重复的节点。

判断一棵树是否为搜索二叉树的方法：

• 方法一：中序遍历整棵树，如果该中序遍历的序列是升序的，则是搜索二叉树，否则不是。

• 方法二：用递归套路解决：

  ①目标：假设以 X 节点为根的二叉树是否为搜索二叉树；

  ②可能性：通过向左树获得某些信息，向右树获得某些信息的情况下来列举可能性；

  ③ X 是搜索二叉树的原则：
  （1）X左树是搜索二叉树；
  （2）X右树是搜索二叉树；
  （3）X左树的最大值 < X节点的值；
  （4）X节点的值 < X 右树的最小值；

  所以对于每一个子树的根节点，只需要上面 4 个信息就能支持判断该子树是否为搜索二叉树。

  整理可得，需要向左树获得信息：1. 是否为搜索二叉树；2. 最大值。

  向右树获得信息：1. 是否为搜索二叉树；2. 最小值。

  此时发现向左树和右树需要获得的信息不一样，怎么办呢？求全集！！

  即是说，向左树和右树都需要获得信息包括（1）是否为搜索二叉树；（2）最大值；（3）最小值。

  递归对所有的节点一视同仁，不要定制任何节点的信息。

3、实现

C++版

/************************************************************************* > File Name: 035.判断二叉树是否为二叉搜索树.cpp > Author: Maureen > Mail: [email protected] > 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;
}

Java 版

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!");
	}
}