判断二叉搜索树的合法性需确保每个节点值在其左右子树构成的范围内，中序遍历结果应为严格递增序列，可通过递归配合区间约束实现，初始范围为(LONG_MIN, LONG_MAX)，左子树更新上限为父节点值，右子树更新下限为父节点值，若节点值超出范围则返回false，该方法时间复杂度O(n)，空间复杂度O(h)，优于需额外数组存储的中序遍历法。
判断二叉搜索树（BST）的合法性，核心是确保每个节点满足BST的性质：左子树所有节点值小于当前节点值，右子树所有节点值大于当前节点值，且左右子树也必须是二叉搜索树。
利用中序遍历判断
二叉搜索树的中序遍历结果是严格递增的。可以通过中序遍历收集节点值，再检查是否有序。
- 进行中序遍历，将节点值存入数组
- 遍历数组，检查是否为严格递增序列
- 时间复杂度 O(n)，空间复杂度 O(n)
示例代码：
bool isValidBST(TreeNode* root) {
vector
inorder(root, values);
for (int i = 1; i
if (values[i]
}
return true;
}
void inorder(TreeNode* root, vector
if (!root) return;
inorder(root->left, values);
values.push_back(root->val);
inorder(root->right, values);
}
递归配合区间约束
更高效的方法是在递归过程中维护一个合法取值范围 [min, max)，每次向下传递更新后的边界。
立即学习“C++免费学习笔记（深入）”；
- 根节点初始范围为 (LONG_MIN, LONG_MAX)
- 左子树的上限是父节点值，右子树的下限是父节点值
- 一旦节点值超出范围，返回 false
示例代码：
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
bool validate(TreeNode* node, long minVal, long maxVal) {
if (!node) return true;
if (node->val val >= maxVal) return false;
return validate(node->left, minVal, node->val) &&
validate(node->right, node->val, maxVal);
}
避免常见错误
直接比较父节点与左右孩子是不够的，必须保证整个子树都满足BST性质。
- 错误写法：只判断 root->left->val val
- 正确做法：使用中序遍历或区间法确保全局有序
- 注意处理重复值，BST通常不允许相等节点
基本上就这些。推荐使用递归加区间约束的方法，效率更高且无需额外存储。
