力扣第98题：验证二叉搜索树 - 中序遍历解法详解

内容简介

本文详细解析了力扣第98题"验证二叉搜索树"的中序遍历解法。通过中序遍历将二叉树的节点值按顺序存储到数组中，然后检查数组是否严格递增来判断是否为有效的二叉搜索树。这种方法直观易懂，时间复杂度为O(n)，是理解BST性质的经典解法。

算法思路

‌1.中序遍历二叉树‌：利用递归实现左-根-右的遍历顺序

‌2.存储节点值‌：将遍历得到的节点值按顺序存入数组

‌3.验证有序性‌：检查数组中元素是否严格递增

4‌.返回结果‌：若严格递增则为有效BST，否则无效

完整代码（带注释）

class Solution {
public:
    vector<int> nums;  // 存储中序遍历结果的数组
    
    // 中序遍历辅助函数
    void inorder(TreeNode* root) {
        if (!root)  // 递归终止条件：空节点
            return;
        inorder(root->left);      // 递归遍历左子树
        nums.push_back(root->val); // 存储当前节点值
        inorder(root->right);     // 递归遍历右子树
    }
    
    // 验证BST的主函数
    bool isValidBST(TreeNode* root) {
        inorder(root);  // 执行中序遍历
        
        // 检查遍历结果是否严格递增
        for (int i = 1; i < nums.size(); i++) 
            if (nums[i] <= nums[i - 1])  // 发现非递增情况
                return false;
        
        return true;  // 全部检查通过则为有效BST
    }
};

复杂度分析

‌时间复杂度‌：O(n)，需要遍历树的所有节点

‌空间复杂度‌：O(n)，需要存储所有节点值（递归栈空间最坏情况也是O(n)）

优化方向

‌无需存储的遍历法‌：可以在遍历时直接比较前驱节点值，节省空间

‌迭代实现‌：用栈代替递归，避免递归带来的额外开销

‌利用BST性质‌：递归检查每个节点是否在合法范围内

总结

本文提供的中序遍历解法是验证二叉搜索树的经典方法，通过将BST的性质转化为数组的有序性检查，思路清晰易懂。理解这种解法后，可以进一步探索更高效的空间优化解法。