题目

解法：中序遍历

思路

核心思想是利用BST中序遍历结果为严格递增序列这一性质，通过递归中序遍历实时检查单调性。

正确性证明：BST的定义保证了左子树所有节点值小于根，右子树所有节点值大于根。根据中序遍历”左-根-右”的顺序，访问顺序必然是从小到大严格递增的。反之，若中序遍历严格递增，则每个节点都满足左子树最大值<当前值<右子树最小值，符合BST定义。因此只需验证遍历序列是否严格递增即可等价判断BST。

• Step 1: 初始化prev为LONG_MIN，记录前一个访问的节点值
• Step 2: 递归遍历左子树，若返回false则提前终止
• Step 3: 检查当前节点值是否大于prev，否则返回false
• Step 4: 更新prev为当前节点值
• Step 5: 递归遍历右子树并返回结果

复杂度

• 时间复杂度: $O(n)$
• 空间复杂度: $O(h)$，其中h为树的高度，递归栈空间消耗

代码

class Solution {
public:
    long long prev = LONG_MIN; // 记录前一个节点的值

    bool isValidBST(TreeNode* root) {
        if (!root) return true;

        if (!isValidBST(root->left)) return false;

        if (root->val <= prev) return false;
        prev = root->val; 
        return isValidBST(root->right);
    }
};