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) {// 如果根节点为空，说明是一棵空树，返回trueif(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)，因为需要存储递归调用的栈。