Leetcode---Validate Binary Search Tree

需要牢记BST的定义：左边的所有节点都小于根节点，根节点小于右边的所有节点

所以这样的做法是错误的：

bool isValidBST(TreeNode *root) {
    if(root==NULL)
        return true;
    bool l=true;
    bool r=true;
    if(root->left!=NULL)
        l=root->val>root->left->val;
    if(root->right!=NULL)
        r=root->val<root->right->val;
    return l&&r&&isValidBST(root->left)&&isValidBST(root->right);
}

而正确的做法应该是中序遍历，查看输出是不是有序的

TreeNode * pre=NULL;
bool isValidBST(TreeNode *root) {
    if(root==NULL)
        return true;
    bool l=isValidBST(root->left);
    if(pre==NULL)
        pre=root;
    else{
        if(root->val<=pre->val){
            return false;
        }
        pre=root;
    }
    bool r=isValidBST(root->right);
    return l&&r;
}

还有一种更直观的

TreeNode * pre=NULL;
bool flag=true;
void f(TreeNode *root) {
    if(root==NULL)
        return;
    f(root->left);
    if(pre==NULL)
        pre=root;
    else{
        if(root->val<=pre->val){
            flag=false;
            return;
        }
        pre=root;
    }
    f(root->right);
    return;
}
bool isValidBST(TreeNode *root) {
    f(root);
    return flag;
}