题解 |NO.34 #判断是不是二叉搜索树#3.11

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
#include <limits.h>
#include <stdbool.h>
long pre = INT_MIN;		//将pre的初值设为无穷小
bool isValidBST(struct TreeNode* root ) {
    // 递归判断左右子树是否为二叉搜索树
    if(root == NULL)	//空结点是二叉搜索树
        return true;
    if(!isValidBST(root->left))		//如果左子树不是二叉搜索树，则整棵树不是
        return false;
    if(root->val <= pre)		//如果当前结点值小于等于前一结点值，则不是二叉搜索树
        return false;
    pre = root->val;		//更新前驱指针
    if(!isValidBST(root->right))	//如果右子树不是二叉搜索树，则整棵树不是
        return false;
    return true;	//全部遍历结束，是二叉搜索树
}

//1.考虑遍历全部是返回false还是返回true，这样才好将半路情况写出来
//2.递归判断，将判断函数放在if()中
//3.使用无穷小或无穷大，用long型，INT_MIN和INT_MAX