98. Validate Binary Search Tree

O(n) inorder traversal
维护一个中序遍历的当前最后一个节点lastNode，遍历完左子树，如果是valid，lastNode应该是左子树最后一个（最大的）节点，将其和root比较，如果比root小，则将lastNode更新为root然后遍历右子树，一个valid的BST必须始终保持lastNode是最大的节点且小于当前root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *lastNode = nullptr;
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (!isValidBST(root->left)) return false;
        if (lastNode && lastNode->val >= root->val) return false;
        lastNode = root;
        return isValidBST(root->right);
    }
};

O(n) dfs判断条件，左子树最大值 < 根节点值 < 右子树最小值，所以递归时需要返回三个值，树的最小值，树的最大值，该树是否是valid

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        auto res = helper(root);
        return res[0] <= res[1];
    }

    vector<int> helper(TreeNode *root) {
        if (!root) return {-1, 1};
        int mn = root->val, mx = root->val;
        if (root->left) {
            auto l = helper(root->left);
            if (l[0] > l[1] || l[1] >= root->val) return {1, -1};
            mn = l[0];
        }
        if (root->right) {
            auto r = helper(root->right);
            if (r[0] > r[1] || root->val >= r[0]) return {1, -1};
            mx = r[1];
        }
        return {mn, mx};
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        bool res = true;
        helper(root, res);
        return res;
    }

    pair<int, int> helper(TreeNode *root, bool &res) {
        if (!root) return {INT_MAX, INT_MIN};
        int max = root->val, min = root->val;
        if (root->left) {
            auto l = helper(root->left, res);
            min = std::min(min, l.first);
            max = std::max(max, l.second);
            res &= (l.second < root->val);
        }
        if (root->right) {
            auto r = helper(root->right, res);
            min = std::min(min, r.first);
            max = std::max(max, r.second);
            res &= (root->val < r.first);
        }
        return {min, max};
    }
};