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

判断二叉搜索树的合法性需确保每个节点值在其左右子树构成的范围内，中序遍历结果应为严格递增序列，可通过递归配合区间约束实现，初始范围为(LONG_MIN, LONG_MAX)，左子树更新上限为父节点值，右子树更新下限为父节点值，若节点值超出范围则返回false，该方法时间复杂度O(n)，空间复杂度O(h)，优于需额外数组存储的中序遍历法。

判断二叉搜索树（BST）的合法性，核心是确保每个节点满足BST的性质：左子树所有节点值小于当前节点值，右子树所有节点值大于当前节点值，且左右子树也必须是二叉搜索树。

利用中序遍历判断

二叉搜索树的中序遍历结果是严格递增的。可以通过中序遍历收集节点值，再检查是否有序。

示例代码：

bool isValidBST(TreeNode* root) {
   vector<int> 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* root, vector<int>& values) {
   if (!root) return;
   inorder(root->left, values);
   values.push_back(root->val);
   inorder(root->right, values);
}

递归配合区间约束

更高效的方法是在递归过程中维护一个合法取值范围 [min, max)，每次向下传递更新后的边界。

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

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

30

查看详情

示例代码：

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);
}

避免常见错误

直接比较父节点与左右孩子是不够的，必须保证整个子树都满足BST性质。

基本上就这些。推荐使用递归加区间约束的方法，效率更高且无需额外存储。

以上就是c++++中如何判断二叉搜索树合法性_c++二叉搜索树合法性判断方法的详细内容，更多请关注php中文网其它相关文章！