LeetCode|LeetCode 98.验证二叉搜索树 LeetCode98.验证二叉搜索树

题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

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

示例示例1

输入: 2 / \ 13 输出: true

示例2

输入: 5 / \ 14 / \ 36 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

题目链接
题目分析
其实很简单，二叉搜索树的中序遍历是一个递增序列，只要对二叉搜索树做一次中序遍历，储存前一个结点的值，并与当前节点做对比，如果前一个结点小于当前节点，那么就继续遍历，否则停止。
【LeetCode|LeetCode 98.验证二叉搜索树】二叉搜索树的中序遍历模板：

void InOrder(TreeNode* root){ if (!root) return ; InOrder(root->left); visit(root->val); // 对当前节点的操作 InOrder(root->right); }

题目解答

class Solution { public: bool res = true; int pre; void InOrder(TreeNode* root, int &flag){ if (!root) return ; InOrder(root->left, flag); if (flag == 0){ pre = root->val; flag = 1; }else { if (pre < root->val) { if (res) res = true; } else { res = false; } pre = root->val; } InOrder(root->right, flag); } bool isValidBST(TreeNode* root) { int flag = 0; InOrder(root, flag); return res; } };