98. Validate Binary Search Tree(M)

题目描述

给定一颗二叉树，判断它是否为搜索二叉树。
搜索二叉树的定义如下：

• 左子树所有的值都小于当前节点
• 右子树所有的值都大于当前节点
• 左子树和右子树都为搜索二叉树

原题以及例子如下，

题目分析

根据搜索二叉树的定义我们可以发现，如果当使用中序遍历时，我们可以得到一个升序的序列，如果这个序列不满足升序的条件，那么它就不是搜索二叉树。具体实现如下(pre代表遍历的前一个结点的值)，

class Solution {
    bool isFirst;
public:
    bool isValidBST(TreeNode* root) {
        int num = INT_MIN;
        isFirst = false;
        return isOk(num, root);
    }
    bool isOk(int& pre, TreeNode* p) {
        if (p == NULL)
            return true;
        if (!isOk(pre, p->left)) {
            return false;
        }
        if (!isFirst) {
            pre = p->val;
            isFirst = true;
        } else {
            if (pre >= p->val) {
                return false;
            }
            pre = p->val;
        }

        return isOk(pre, p->right);
    }
};