LeetCode 98. 验证二叉搜索树（中序遍历）

示例 1:

输入:
    2
   / \
  1   3
输出: true
示例 2:

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

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        long prev = INT64_MIN;
        bool valid = true;
        isValid(root, prev, valid);
        return valid;
    }
    void isValid(TreeNode* root, long &prev, bool &valid)
    {
        if(!valid || !root)
            return;
        isValid(root->left, prev, valid);
        if(valid)
            valid = (root->val > prev);
        prev = root->val;
        isValid(root->right, prev, valid);
    }
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        long prev = INT64_MIN;
        bool valid = true;
        stack<TreeNode*> stk;
        TreeNode *cur = root;
        while(cur != NULL || !stk.empty())
        {
            while(cur != NULL)
            {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            if(cur->val <= prev)
                return false;
            prev = cur->val;
            cur = cur->right;
        }
        return valid;
    }
};