题解 | #判断是不是二叉搜索树#

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    //本题采用二叉树的树形dp套路
    //首先分析一下需要什么信息
    //需要知道左右子树是否都是搜索二叉树
    //需要知道左子树的最大值和右子树的最小值以便和根节点对比判断是否满足搜索二叉树的特点
    //统一一下需要如下信息：左右子树是否都是搜索二叉树，左右子树的最大值和最小值
    struct returnType{
        bool isBST;
        int max,min;
    };
    //该函数的作用为判断一颗二叉树是否是二叉搜索树
    int Max(int a,int b){
        return a>b?a:b;
    }
    int Min(int a,int b){
        return a<b?a:b;
    }
    returnType* isBST(TreeNode*root){
        if(root==NULL)//空树认为是搜索二叉树
            return NULL;//用空节点代表是空树的情况
        returnType*leftData=isBST(root->left);//获取左子树的信息
        returnType*rightData=isBST(root->right);//获取右子树的信息
        //把所有isBST可能为false的情况列举出来
        bool isBST=true;
        if(leftData&&leftData->isBST==false)
            isBST=false;
        if(rightData&&rightData->isBST==false)
            isBST=false;
        if(leftData&&leftData->max>=root->val)
            isBST=false;
        if(rightData&&rightData->min<=root->val)
            isBST=false;
        //计算root返回时的最大值和最小值
        int max=root->val;
        int min=root->val;
        if(leftData&&rightData){//左右子树的返回值都不为空的话
            max=Max(max, Max(leftData->max, rightData->max));
            min=Min(min,Min(leftData->min, rightData->min));
        }
        else if(!leftData&&rightData){//左子树返回的信息为空
            max=Max(max, rightData->max);
            min=Min(min, rightData->min);
        }
        else if(!rightData&&leftData){//右子树返回的信息为空
            max=Max(max, leftData->max);
            min=Min(min, leftData->min);
        }
        returnType*data=new returnType;
        data->isBST=isBST;
        data->min=min;
        data->max=max;
        return data;
    }
    bool isValidBST(TreeNode* root) {
        // write code here
        return isBST(root)->isBST;
    }
};