c++中如何判断二叉搜索树是否合法_c++二叉搜索树合法性判断

判断二叉搜索树合法性的核心是确保每个节点值在其子树的取值范围内，可通过中序遍历验证序列是否严格递增，或使用递归配合上下界约束。推荐后者，初始范围为(LONG_MIN, LONG_MAX)，左子树更新上界为当前节点值，右子树更新下界为当前节点值，时间复杂度O(n)，空间复杂度O(h)，避免仅比较父子节点的错误方法。

判断一个二叉搜索树（BST）是否合法，核心是确保每个节点满足二叉搜索树的性质：对于任意节点，其左子树中所有节点值都小于该节点值，右子树中所有节点值都大于该节点值，并且左右子树也必须是合法的二叉搜索树。

使用中序遍历判断

二叉搜索树的一个重要性质是：中序遍历结果是严格递增的序列。因此可以通过中序遍历来验证合法性。

实现思路：

• 进行中序遍历，将节点值依次存入数组
• 检查数组是否为严格递增

#include 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
bool isValidBST(TreeNode* root) {
std::vector values;
inorder(root, values);
for (int i = 1; i < values.size(); ++i) {
if (values[i] <= values[i-1]) 
return false;
}
return true;
}
void inorder(TreeNode* node, std::vector& values) {
if (!node) return;
inorder(node->left, values);
values.push_back(node->val);
inorder(node->right, values);
}

递归法配合上下界约束

更高效的方法是在递归过程中维护每个节点允许的取值范围（最小值和最大值），一旦超出范围就返回false。

立即学习“C++免费学习笔记（深入）”；

WPS AI

金山办公发布的AI办公应用，提供智能文档写作、阅读理解和问答、智能人机交互的能力。

下载

关键点：

• 根节点初始范围是 (LONG_MIN, LONG_MAX)
• 进入左子树时，更新上界为当前节点值
• 进入右子树时，更新下界为当前节点值

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 <= minVal || node->val >= maxVal) 
return false;
return validate(node->left, minVal, node->val) &&
validate(node->right, node->val, maxVal);
}

避免常见错误

以下写法是错误的：

// 错误：只比较当前节点与左右孩子
if (root->left && root->left->val >= root->val) return false;
if (root->right && root->right->val <= root->val) return false;

这种做法无法检测左子树中出现大于根节点的值等情况，必须保证整个子树都在有效范围内。

基本上就这些。推荐使用递归配合上下界的方法，时间O(n)，空间O(h)，逻辑清晰且效率高。