98. Validate Binary Search Tree

98. Validate Binary Search Tree

中序遍历BST是元素从小到达排列的，因此如果未严格单调递增，就是无效的BST

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* pre = nullptr;
        while(!s.empty() || root)
        {
            while(root)
            {
                s.push(root);
                root = root->left;
            }
            auto p = s.top();
            s.pop();
            if(pre && pre->val >= p->val)
                return false;
            pre = p;
            root = p->right;
        }
        return true;
    }
};

每个左点的上界为父节点，下界则沿用上一节点，右点的下界为父节点，上界则沿用上衣节点，这样可以保证界限是由上面传递下来的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MAX, LONG_MIN);
    }
private:
    bool helper(TreeNode* node, long max, long min)
    {
        if(!node)
            return true;
        if(node->val >= max || node->val <= min)
            return false;
        else
            return helper(node->left, node->val, min) && helper(node->right, max, node->val);
    }
};