当前位置：首页 > ds >正文

leetcode题解98：验证二叉搜索树。（中序遍历！！！BST要点！）

ds 2025/8/18 2:05:27

一、题目内容

题目要求判断给定的二叉树是否是一个有效的二叉搜索树（BST）。有效二叉搜索树的定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身也必须是二叉搜索树。

二、题目分析

输入和输出

输入：一个二叉树的根节点 root。
输出：一个布尔值，表示该二叉树是否是一个有效的二叉搜索树。

递归函数 `isValidBST` 的逻辑

基本情况：

如果当前节点为空（root == NULL），返回 true，因为空树是有效的二叉搜索树。

递归检查左子树：

递归调用 isValidBST(root->left)，检查左子树是否为有效的二叉搜索树。

检查当前节点：

使用一个全局变量 pre 来记录中序遍历的前一个节点。

如果 pre 不为空且 pre->val >= root->val，则当前节点不满足二叉搜索树的条件，返回 false。更新 pre 为当前节点。

递归检查右子树：

递归调用 isValidBST(root->right)，检查右子树是否为有效的二叉搜索树。

返回结果：

返回左子树和右子树检查的结果的逻辑与（left && right）。

三、解题要点

1. 二叉搜索树的定义

左子树：左子树上所有节点的值都小于当前节点的值。
右子树：右子树上所有节点的值都大于当前节点的值。
递归性质：左子树和右子树本身也必须是二叉搜索树。

2. 中序遍历的性质

中序遍历：中序遍历二叉搜索树的结果是一个递增的有序序列。
利用中序遍历：通过中序遍历，可以方便地检查当前节点是否满足二叉搜索树的条件。如果当前结点与前一个结点不是递增关系，则不符合二叉搜索树的要求。

3. 使用递归

递归思想：递归是解决二叉树问题的常用方法。通过递归，可以逐层检查每个节点是否满足二叉搜索树的条件。
递归终止条件：当当前节点为空时，返回 true，因为空树是有效的二叉搜索树。

4. 使用辅助变量

辅助变量 pre：记录中序遍历的前一个节点。通过比较当前节点和前一个节点的值，可以判断当前节点是否满足二叉搜索树的条件。
更新 pre：在每次递归调用返回后，更新 pre 为当前节点。

5. 递归逻辑

递归检查左子树：

递归调用 isValidBST(root->left)，检查左子树是否为有效的二叉搜索树。如果左子树不是有效的二叉搜索树，直接返回 false。

检查当前节点：

如果 pre 不为空且 pre->val >= root->val，则当前节点不满足二叉搜索树的条件，返回 false。更新 pre 为当前节点。

递归检查右子树：

递归调用 isValidBST(root->right)，检查右子树是否为有效的二叉搜索树。如果右子树不是有效的二叉搜索树，直接返回 false。

返回结果：

返回左子树和右子树检查的结果的逻辑与（left && right）。

四、中序遍历的详细讲解

1. 中序遍历的定义

中序遍历：中序遍历二叉树的顺序是：左子树 -> 当前节点 -> 右子树。
中序遍历的结果：对于二叉搜索树，中序遍历的结果是一个递增的有序序列。

2. 利用中序遍历检查二叉搜索树

核心思想：在中序遍历过程中，当前节点的值应该大于前一个节点的值。
实现方法：
- 使用一个全局变量 pre 来记录中序遍历的前一个节点。
- 在递归过程中，首先递归检查左子树，然后检查当前节点是否满足条件，最后递归检查右子树。
- 如果在任何时候发现 pre->val >= root->val，则当前节点不满足二叉搜索树的条件，返回 false。

3. 中序遍历的递归逻辑

递归检查左子树：
- 递归调用 isValidBST(root->left)，检查左子树是否为有效的二叉搜索树。
- 如果左子树不是有效的二叉搜索树，直接返回 false。
检查当前节点：
- 如果 pre 不为空且 pre->val >= root->val，则当前节点不满足二叉搜索树的条件，返回 false。
- 更新 pre 为当前节点。
递归检查右子树：
- 递归调用 isValidBST(root->right)，检查右子树是否为有效的二叉搜索树。
- 如果右子树不是有效的二叉搜索树，直接返回 false。

五、代码解答

1. C++ 代码

class Solution {
public:TreeNode* pre = NULL; // 用于记录中序遍历的前一个节点bool isValidBST(TreeNode* root) {// 如果当前节点为空，返回 trueif (root == NULL) return true;// 递归检查左子树bool left = isValidBST(root->left);// 检查当前节点是否满足二叉搜索树的条件，如果不符合递增条件，则不是二叉搜索树if (pre != NULL && pre->val >= root->val) {return false;}// 更新 pre 为当前节点pre = root;// 递归检查右子树bool right = isValidBST(root->right);// 返回左子树和右子树检查的结果return left && right;}
};

2. 详细注释

成员变量
- TreeNode* pre = NULL：用于记录中序遍历的前一个节点。
- bool isValidBST(TreeNode* root)：主函数，用于递归判断二叉树是否为有效的二叉搜索树。
递归函数 isValidBST
- 基本情况：如果当前节点为空，返回 true。
- 递归检查左子树：递归调用 isValidBST(root->left)，检查左子树是否为有效的二叉搜索树。
- 检查当前节点：如果 pre 不为空且 pre->val >= root->val，则当前节点不满足二叉搜索树的条件，返回 false。更新 pre 为当前节点。
- 递归检查右子树：递归调用 isValidBST(root->right)，检查右子树是否为有效的二叉搜索树。
- 返回结果：返回左子树和右子树检查的结果的逻辑与。
回溯和递归的详细解释
- 递归：递归是一种函数调用自身的方法，用于解决复杂问题。在本题中，递归用于中序遍历二叉树，检查每个节点是否满足二叉搜索树的条件。
- 终止条件：递归的终止条件是当前节点为空。
- 回溯：在递归调用返回后，通过更新 pre 的值，恢复到当前节点的状态，确保每次递归返回后，状态正确，不会影响后续的递归调用。