【2024考研】题解23 | #判断是不是二叉搜索树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <climits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool recursion(int lv,TreeNode* root,int rv){
        //special case
	    if(root == NULL) 
            return true;
	   //反正——左 < 根 < 右
        if(root->val < lv || root->val > rv) 
            return false;
        return recursion( lv, root->left, root->val) && recursion( root->val, root->right, rv);
    }
    bool isValidBST(TreeNode* root) {
        // write code here
        //反正——左 < 根 < 右
        return recursion(INT_MIN,root,INT_MAX);
    }
};

基本算法思路：

- 使用递归的方式判断一棵二叉树是否是有效的二叉搜索树。

- 首先判断特殊情况，如果根节点为空，则返回true。

- 定义一个递归函数，该函数接受当前节点、当前节点的左边界和右边界作为参数。

- 如果当前节点为空，则返回true。

- 如果当前节点的值小于左边界或大于右边界，则返回false。

- 递归判断当前节点的左子树是否是有效的二叉搜索树，左边界不变，右边界更新为当前节点的值。

- 递归判断当前节点的右子树是否是有效的二叉搜索树，左边界更新为当前节点的值，右边界不变。

- 返回左子树和右子树的结果的逻辑与运算结果。

时间复杂度：

O(n)，其中n是二叉树的节点个数。需要遍历每个节点一次。

空间复杂度：

O(n)，递归调用栈的深度最大为二叉树的高度，最坏情况下，二叉树是一个链表，高度为n，因此空间复杂度是O(n)。