验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

98. 验证二叉搜索树 - 力扣（LeetCode）

解题思路

要判断一个二叉树是否是有效的二叉搜索树（BST），我们需要确保每个节点都满足BST的定义：节点的左子树只包含小于当前节点的数，节点的右子树只包含大于当前节点的数，并且所有左子树和右子树自身也必须是BST。

递归是解决这个问题的有效方法。递归的基本思路是：

递归函数定义：
- 定义一个递归函数 isValidBST(TreeNode* node, long long lower, long long upper)，其中 node 是当前节点，lower 是当前节点允许的最小值，upper 是当前节点允许的最大值。
- 初始调用时，lower 可以设为负无穷大（例如 LONG_LONG_MIN），upper 可以设为正无穷大（例如 LONG_LONG_MAX）。
递归终止条件：
- 如果当前节点为空，返回 true，因为空树是BST。
- 如果当前节点的值小于等于 lower 或大于等于 upper，返回 false，因为当前节点的值不满足BST的定义。
递归调用：
- 递归检查左子树，更新 upper 为当前节点的值（因为左子树的所有节点值必须小于当前节点）。
- 递归检查右子树，更新 lower 为当前节点的值（因为右子树的所有节点值必须大于当前节点）。
返回结果：
- 如果左子树和右子树都满足BST的定义，返回 true。

class Solution {
public:bool isValidBST(TreeNode* node, long long lower = LONG_LONG_MIN,long long upper = LONG_LONG_MAX) {// 空节点是BSTif (node == nullptr) {return true;}// 当前节点的值不在允许的范围内，不是BSTif (node->val <= lower || node->val >= upper) {return false;}// 递归检查左子树和右子树return isValidBST(node->left, lower, node->val) &&isValidBST(node->right, node->val, upper);}
};

详细解释

函数签名：
- isValidBST(TreeNode* node, long long lower = LONG_LONG_MIN, long long upper = LONG_LONG_MAX)：
  - node 是当前节点。
  - lower 是当前节点允许的最小值，初始为 LONG_LONG_MIN。
  - upper 是当前节点允许的最大值，初始为 LONG_LONG_MAX。
递归终止条件：
- if (node == nullptr) { return true; }：空节点是BST。
- if (node->val <= lower || node->val >= upper) { return false; }：当前节点的值不在允许的范围内，不是BST。
递归调用：
- isValidBST(node->left, lower, node->val)：检查左子树，更新 upper 为当前节点的值。
- isValidBST(node->right, node->val, upper)：检查右子树，更新 lower 为当前节点的值。
返回结果：
- return isValidBST(node->left, lower, node->val) && isValidBST(node->right, node->val, upper);：如果左子树和右子树都满足BST的定义，返回 true。