题目描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
解题思路
要判断一个二叉树是否是有效的二叉搜索树(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
。
- 如果左子树和右子树都满足BST的定义,返回
class Solution {
public:
bool isValidBST(TreeNode* node, long long lower = LONG_LONG_MIN,
long long upper = LONG_LONG_MAX) {
// 空节点是BST
if (node == nullptr) {
return true;
}
// 当前节点的值不在允许的范围内,不是BST
if (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
。