leetcode 98 验证二叉搜索树

原题传送门—>>

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

思路：二叉搜索树即为：中序遍历结果为升序的树

这里采用非递归遍历

class Solution {
public:
    int pre = 0;
    int cur = 0;
    int counter = 0;
    stack<TreeNode*> S;
    bool isValidBST(TreeNode* root) {
        TreeNode* p = root;
        while(!S.empty() || p)
        {
            while(p)
            {
                S.push(p);
                p = p->left;
            }
            pre = cur;
            p = S.top();
            cur = p->val;
            if(counter)
            {
                if(pre >= cur)
                    return false;
            }
            ++counter;
            S.pop();
            p = p->right;

        }

        return true;
    }
};