LeetCodehot 力扣热题100 验证二叉搜索树

class Solution {
    vector<int> nums;  // 用来存储二叉树节点值的数组
public:
    bool isValidBST(TreeNode* root) {
    
        inorder(root);  // 中序遍历二叉树，填充 nums 数组
        // 遍历 nums 数组，检查是否为严格递增序列
        for(int i=0; i<nums.size()-1; i++){
            if(nums[i] >= nums[i+1]){  // 如果当前元素不小于下一个元素，说明不是严格递增的
                return false;  // 不是有效的二叉搜索树
            }
        }
        return true;  // 如果整个数组都是严格递增的，说明是有效的二叉搜索树
    }

private:
    // 中序遍历：遍历树的左子树、根节点和右子树
    void inorder(TreeNode* root){
        if(root != nullptr){  // 如果当前节点不是空节点
            inorder(root->left);  // 递归遍历左子树
            nums.push_back(root->val);  // 将当前节点的值加入 nums 数组
            inorder(root->right);  // 递归遍历右子树
        }
    }
};

这段代码是一个验证二叉搜索树（BST）是否有效的算法。通过中序遍历二叉树，将节点的值存储在一个数组中，然后检查数组是否是严格递增的。二叉搜索树的性质是：左子树的值小于根节点的值，右子树的值大于根节点的值，而中序遍历会得到一个按升序排列的节点值序列。

思路：

1. 中序遍历：首先我们要遍历二叉树，使用中序遍历。对于一棵合法的二叉搜索树，使用中序遍历会得到一个严格递增的节点值序列。

2. 将节点值存储到数组：通过递归进行中序遍历，将每个节点的值按顺序存储到一个数组 nums 中。

3. 验证递增性：中序遍历完成后，检查 nums 数组中的值是否是严格递增的。如果有任何两个相邻的元素不满足递增条件，返回 false，表示这不是一棵有效的二叉搜索树。

4. 返回结果：如果数组是严格递增的，说明这棵树符合二叉搜索树的要求，返回 true。

运行步骤：

假设我们有以下二叉树：

      2

     / \

    1   3

1. 初始状态：

• nums 数组为空。

2. 执行 inorder(root)：

• 调用 inorder(2)，根节点是 2。

• 递归调用 inorder(1)（左子树）。

• 在 inorder(1) 中，递归调用 inorder(null)（空左子树），然后将 1 加入 nums 数组。

• 返回并继续遍历右子树（inorder(null)），没有元素。

• 现在，nums = [1]。

• 返回 inorder(2)，将 2 加入 nums 数组。

• 继续遍历右子树，调用 inorder(3)。

• 在 inorder(3) 中，递归调用 inorder(null)（空左子树），将 3 加入 nums 数组。

• 继续遍历右子树（inorder(null)），没有元素。

• 现在，nums = [1, 2, 3]。

• inorder 遍历结束后，nums = [1, 2, 3]。

3. 执行递增性检查：

• nums = [1, 2, 3]。

• 遍历数组：

• 比较 nums[0] 和 nums[1]，即 1 和 2，1 < 2，继续检查。

• 比较 nums[1] 和 nums[2]，即 2 和 3，2 < 3，继续检查。

• 所有检查都通过，返回 true。

边界情况：

• 空树：如果根节点是空的，inorder 函数不会执行任何操作，nums 数组会保持为空。此时，直接返回 true，因为空树是有效的二叉搜索树。

• 只有一个节点的树：即使树只有一个节点，nums 数组也只会包含一个元素，严格递增性自然成立，返回 true。

时间复杂度：

• 中序遍历：时间复杂度是 O(n)，其中 n 是树中节点的数量，因为我们遍历了每个节点一次。

• 数组检查：时间复杂度是 O(n)，需要检查 nums 数组中的所有元素。

• 总的时间复杂度：O(n)。

空间复杂度：

• 我们使用了一个 nums 数组来存储树的节点值，空间复杂度是 O(n)，其中 n 是树中节点的数量。