BST 中序遍历是单调递增的

中序遍历的思路对了，不过代码实现遇到了一点问题，看了一个评论区的代码。

class Solution {
private:
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        bool L = isValidBST(root->left);
        
        if (root->val <= prev) return false;
        prev = root->val;
        
        bool R = isValidBST(root->right);
        return L && R;
    }
};

April 10, 2024

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        dfs(root);
        return res;
    }

    bool flag= true;
    long pre = LONG_MIN;
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        if (root->val <= pre) flag = false;
        pre = root->val;
        dfs(root->right);
    }
};

// 2024-03-06 中序遍历迭代 方式
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        long pre = LONG_MIN;
        while (root || !st.empty()) {
            if (root) {
                st.push(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();
                if (root->val <= pre) {
                    return false;
                }
                pre = root->val;
                root = root->right;
            }
        }
        return true;
    }
};

另外一种思路是官方解答的递归

root->val 要在 (lower, upper) 范围内，初始化为 (LONG_MIN, LONG_MAX)

就是左子树是 (lower, root->val) 右子树 (root->val, upper) 再下一层继续，就是往左走就更新右边界，往右走就更新左边界

class Solution {
    bool helper(TreeNode* root, long lower, long upper) {
        if (!root) return true;
        if (root->val <= lower || root->val >= upper) {
            return false;
        }
        bool a = helper(root->left, lower, root->val);
        bool b = helper(root->right, root->val, upper);
        return a && b;
    }
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};