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

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

bool isValidBST(TreeNode* root) {
    return validate(root, LONG_MIN, LONG_MAX);
}
<p>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);
}</p>

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