【LeetCode二叉树#14】验证二叉搜索树（巩固迭代中序遍历#1）

验证二叉搜索树

力扣题目链接(opens new window)

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

98.验证二叉搜索树

错误思路

根据二叉搜索树的定义：根节点的左子树的值都小于根节点值，右子树的值都大于根节点值

那么就想，可以让根节点（当前节点）的值与其左右子节点的值比较

如果满足条件就是二叉搜索树

if(root->val > root->left->val && root->val < root—>right->val){
    return true;
}
return false;

但是

这种方法有漏洞，并不能覆盖所有出现的情况

例如：

乍一看好像都满足二叉搜索树的条件

但是以10为根节点来看就会出问题，10的右子树中不应该出现比10小的数（也就是6）

因此该树不满足条件

转换为有序数组

利用二叉搜索树的特性对其进行其中序遍历（一定是中序遍历）

所得结果是一个数组，理论上它是递增的

例如：

遍历所得为：[5（向左遍历）,10（回溯）,11（向右遍历再向左遍历）,15（回溯）,20（向右遍历）]

因此我们只需要去判断遍历二叉树的结果数组是否为递增的即可判断该树是否是二叉搜索树

代码分析

1、确定递归函数的参数和返回值

输入参数是根节点，然后我们需要不断递归遍历，往数组中添加元素（操作数组）

因此没有返回值（搜索整颗二叉树，保存每个节点的值，不需要返回值，详见路径总和）

vector<int> saveVal;
void traversal(TreeNode* root){//中序遍历，递归

}

2、确定终止条件

二叉搜索树可以为空

vector<int> saveVal;
void traversal(TreeNode* root){//中序遍历，递归
    //确定终止条件
    if(root == NULL) return true;//根节点为空也算二叉搜索树
}

3、处理单层逻辑

按中序遍历逻辑进行递归遍历

vector<int> saveVal;
void traversal(TreeNode* root){//中序遍历，递归
    //确定终止条件
    if(root == NULL) return true;//根节点为空也算二叉搜索树
    
    //处理单层逻辑
    //左
    traversal(root->left);
    //中，保存节点值
    saveVal.push_back(root->val);
    //右
    traversal(root->right);
}

完整代码

在主函数中调用递归函数遍历整颗二叉树，得到结果数组后判断其是否为递增数组，是即可判断为二叉搜索树

class Solution {
private:
    vector<int> saveVal;
    void traversal(TreeNode* root){
        //确定终止条件
        if(root == NULL) return;//注意，无返回值

        //确定单层处理逻辑
        //中序遍历，递归法
        //左
        traversal(root->left);
        //中，保存节点值
        saveVal.push_back(root->val);
        //右
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        traversal(root);
        //判断结果数组是否是递增的
        // cout << saveVal.size() << endl;//3
        for(int i = 0; i < saveVal.size() - 1; ++i){
            if(saveVal[i] >= saveVal[i + 1]){//如果是saveVal[i - 1] <= saveVal[i],上面就不用减1
                return false;
            }
        }
        return true;
    }
};

注意：
使用size()取数组大小，返回值是从1开始的

纯递归

思路就是先取设定一个变量作为最大值（初始值为系统最小值）

然后通过递归的方式进行中序遍历，不断更新最大值变量

理论上，最大值变量只会越更新越大，即当前最大值永远小于遍历到的新值

如果当前遍历值小于等于最大值变量的话，那么该二叉树不满足二叉搜索树的条件

代码分析

1、确定递归函数的参数和返回值

根据需求，我们有可能会遍历完整颗二叉树，并且当发现不满足条件的情况时，需要立刻返回

因此输入参数是根节点，返回值是布尔值

class Solution {
public:
    //定义最大值变量
    long long maxValue = LONG_MIN; // 因为后台测试数据中有int最小值,所以不能设置为INT_MIN
    bool isValidBST(TreeNode* root) {
		
    }
};

2、确定终止条件

当根节点为空时，可终止。因为二叉搜索树可以为空

class Solution {
public:
    //定义最大值变量
    long long maxValue = LONG_MIN; // 因为后台测试数据中有int最小值,所以不能设置为INT_MIN
    bool isValidBST(TreeNode* root) {
        //确定终止条件
		if(root == NULL) return true;
    }
};

3、确定单层处理逻辑

使用递归中序遍历，不断更新maxValue并与当前遍历值比较

class Solution {
public:
    //定义最大值变量
    long long maxValue = LONG_MIN; // 因为后台测试数据中有int最小值,所以不能设置为INT_MIN
    bool isValidBST(TreeNode* root) {
        //确定终止条件
		if(root == NULL) return true;
        
        //确定单层处理逻辑
        //递归中序遍历
        //左
        bool left = isValidBST(root->left);
        //中，更新并比较最大值
        if (maxValue < root->val) maxValue = root->val;
        else return false;
        
        //右
        bool right = isValidBST(root->right);
 		
        return left && right;
    }
};

迭代法

核心逻辑是，使用中序遍历的迭代法遍历，同时定义当前节点指针和前一节点指针

通过递归不断将节点加入栈中，当遍历到最底层时，弹出栈中的节点进行比较

如果前一节点存在且当前节点小于前一节点，不满足条件

否则继续向右遍历

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        //定义栈
        stack<TreeNode*> st;
        //定义两个指针
        TreeNode* cur = root;//指向根节点
        TreeNode* pre = NULL;
        while(cur != NULL || !st.empty()){
            if(cur != NULL){//判断是否遍历到最底层
                //压栈
                st.push(cur);
                cur = cur->left;//继续向左遍历
            }else{//当遍历到了左边的最底层，开始出栈
                cur = st.top();
                st.pop();
                if(pre != NULL && pre->val >= cur->val) return false;//
                pre = cur;//更新指针，保存前一个节点
                cur = cur->right;//继续向右遍历
            }
        }
        return true;
    }
};