leetcode-98-验证二叉搜索树
目录
leetcode 98 验证二叉搜索树
一、题目描述
二、解题思路
整体思路
二叉搜索树的中序遍历序列是单调递增的，我们可以根据这个原则来判断当前的二叉树是否为二叉搜索树。由于要借助中序遍历的方法，所以我们借助递归来解决这个问题。
具体思路
考虑到空间的开销，我们无需申请数组来寄存中序遍历的序列，可以设置一个全局变量pre，来记录前一个数值，辅助判断。
**(1)函数功能：**isValidBST函数用于判断以root为根节点的二叉树是否为二叉搜索树；
**(2)递归出口：**当root为空节点时，直接返回true
(3)函数体：
**<1>处理左子树，判断左子树是否为二叉搜索树。**当左子树不为二叉搜索树，直接返回false，进行左剪枝；
**<2>处理当前节点。**判断当前节点的值是否大于pre，更新pre的值；
**<3>处理右子树，判断右子树是否为二叉搜索树。**当右子树不为二叉搜索树，直接返回false，进行右剪枝。
**(4)**返回left&&cur&&right即可。
三、代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
long pre=LONG_MIN;
public:
bool isValidBST(TreeNode* root) {
//边界处理
if(root==nullptr) return true;
//处理左子树
bool left=isValidBST(root->left);
if(left==false) return false;//左剪枝
//处理本身
bool cur=true;
if(root->val<=pre) cur=false;
pre=root->val;
//处理右子树
bool right=isValidBST(root->right);
if(right==false) return false;//右剪枝
return left&&cur&&right;
}
};