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来记录中序遍历过程中的前一个节点，以确保每个节点的值都大于前一个节点的值。这里简要解释一下代码的工作流程：
- 定义一个全局变量
pre用于记录中序遍历过程中的前一个节点。- 定义一个辅助函数
isValidBST，它接受当前节点作为参数。- 首先检查当前节点是否为空，如果是，返回
true。- 递归地检查左子树，并返回其结果。
- 如果当前节点的值小于等于中序遍历的前一个节点值
pre，返回false。- 更新
pre为当前节点。- 递归地检查右子树，并返回其结果。
- 返回左右子树都满足条件的布尔值。
这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。