题目

题解

TreeNode的定义：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

1. 直接递归法

class Solution {//三种方法。1、直接递归。利用二叉搜索树的性质
public:
    bool isValidBST(TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);
        //直接调用递归函数，LONG_MIN,LONG_MAX表示long的最小和最大值
    }
    
    bool helper(TreeNode* root,long min,long max){//注意要用long，要oj会报错
        if(!root) return true;//如果root为空，则是二叉搜索树
        if(root->val <= min || root->val >= max) return false;
        //如果root大于最大或者小于最小，返回false。
        return helper(root->left,min,root->val) && helper(root->right,root->val,max);
        //对左右子树进行递归，并改变最小最大值。
        //进入左子树变最大值为根节点，进入右子树变最小值为根节点。
        //这样与直接比较左<根<右不同，是按照二叉搜索树的性质比较的。
    }
};

2. 递归中序遍历

class Solution {//三种方法。2、递归中序遍历。二叉搜索树的中序遍历是升序数组
TreeNode* pre = nullptr;
//在private中定义pre用来存储上一个遍历到的值。（由于引入了相等的情况，在isVaildBST中定义pre会出错）
public:
    bool isValidBST(TreeNode* root) {
        return inorder(root);//调用递归
    }

    bool inorder(TreeNode* node){
        if(!node) return true;//节点为空，返回true
        if(!inorder(node->left)) return false;//中序遍历，先判断左子树
        if(pre && node->val <= pre->val) return false;//然后是中间的节点
        pre = node;//比较完把node的值赋给pre
        if(!inorder(node->right)) return false;//最后是右子树，也有把这一句放return的，但我感觉这样表达更容易理解。
        return true;//都没出现报错的情况则返回true
    }
};

3. 非递归中序遍历

其主要结构与#94类似，主要是修改了存值的部分。其他的细节未注释，详见#94

class Solution {//三种方法。3、非递归中序遍历。二叉搜索树的中序遍历是升序数组
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;//创建用于遍历的栈
        TreeNode *cur = root, *pre = nullptr;//创建cur指向根节点，pre用于暂存上一个值
        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            }
            else{
                cur = s.top();s.pop();
                if(pre && pre->val >= cur->val) return false;
                pre = cur;
                //这里是与#94的主要区别。#94存数，这一题进行判断并重新设置pre
                cur  = cur->right;
            }
        }
        return true;
    }
};