181.二叉树：验证二叉树（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 用于记录中序遍历过程中的前一个节点
    TreeNode* pre = nullptr;

    bool isValidBST(TreeNode* root) 
    {
        // 如果根节点为空，说明是一棵空树，返回true
        if(root == nullptr) return true;

        // 遍历左子树
        bool left = isValidBST(root->left);

        // 如果当前节点的值小于等于中序遍历的前一个节点值（pre）
        if(pre != nullptr && pre->val >= root->val)
            return false; // 不满足BST定义，返回false

        // 更新前一个节点为当前节点
        pre = root;

        // 继续遍历右子树
        bool right = isValidBST(root->right);

        // 返回左右子树是否都满足BST的结果
        return left && right;
    }
};

代码使用了递归的方法。主要思路是从根节点开始，递归地检查左右子树。在递归过程中，使用一个全局变量 pre 来记录中序遍历过程中的前一个节点，以确保每个节点的值都大于前一个节点的值。

这里简要解释一下代码的工作流程：

1. 定义一个全局变量 pre 用于记录中序遍历过程中的前一个节点。
2. 定义一个辅助函数 isValidBST，它接受当前节点作为参数。
3. 首先检查当前节点是否为空，如果是，返回 true。
4. 递归地检查左子树，并返回其结果。
5. 如果当前节点的值小于等于中序遍历的前一个节点值 pre，返回 false。
6. 更新 pre 为当前节点。
7. 递归地检查右子树，并返回其结果。
8. 返回左右子树都满足条件的布尔值。

这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。