LeetCode:是否是合法的二叉搜索树

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思路：
可以观察到，如果一个树的中序遍历序列是递增的，那么该树是二叉搜索树。因此可以用中序遍历来解决。中序遍历序列只需维护一个 当前结点的前一个结点的数值，比较两者大小，并更新即可。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        stack<TreeNode *> s;
        TreeNode *cur=root;
        long pre=LONG_MIN;  //用于记录前一个结点的值，首先存储为最小值
        while(!s.empty()||cur!=NULL)
        {
            if(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            else
            {
                TreeNode *tmp=s.top();
                s.pop();

                //原非递归版本打印的部分，换成判断部分
                if(pre>=tmp->val)
                    return false;
                pre=tmp->val; //更新

                cur=tmp->right;
            }
        }
        return true;
    }
};

pre之所以定义为 long类型是因为，测试用例提供了一个int型的最小值输入[[-2147483648]]，和pre相等，会被判断为false。