力扣-98.验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

class Solution {
public:long long min = LONG_LONG_MIN;//测试数据中有INT_MINbool isValidBST(TreeNode *root) {if (!root)return true;bool left = isValidBST(root->left);if (root->val > min) {min = root->val;} else {return false;}bool right = isValidBST(root->right);return left && right;}
};

小结：这道题的坑就在于左子树是二叉搜索树+右子树是二叉搜索树+左子树根结点<根结点<右子树根结点，此时整棵树依然不能确定是否为二叉搜索树。我们来看这样一个例子：[5，4，6，null，null，3，7] 这里3 < 5就不满足条件。解决方法是利用中序遍历+一个变量记录遍历到的值，如果不满足直接返回false，因为二叉搜索树的中序遍历是递增的序列。