c++ - 测试树是否为二叉搜索树

标签 c++ algorithm tree binary-search-tree

<分区>

我知道我不应该在这里问这些类型的问题，但我被困住了，无法弄清楚问题所在。所以，我写了这段代码，它将树的根作为输入，并检查给定的树是否是 BST。但是我没有通过几个测试用例，我不明白为什么？如果有人能告诉我我的代码有什么问题，将不胜感激。这是问题 Is This a Binary Search Tree? 的链接

这是代码。

bool checkBST(Node* root) {
    if(root == NULL)
        return false;


        int d = root->data;
        bool r1 = true,r2=true;
        if(root->left != NULL){
            if(d < root->left->data)
                r1 = false;
            else
                r1 = checkBST(root->left);

        }

        if(root->right != NULL){
            if(d > root->right->data)
                r2 = false;
            else
                r2 = checkBST(root->right);
        }
        return r1 && r2;

    }

最佳答案

问题可能是您仅根据其父节点检查每个节点。请记住，整个子树必须位于父树的任一侧。

如

这将传递您的代码。每个子项都是与其直接父项相关的正确值。但是 12 比根 10 大，但在左子树中。

#include <climits>

bool checkBST(Node* root, int min, int max) {
    if (!root) {return true;}

    return (min <= root->data && root->data <= max)
        && checkBST(root->left, min, root->data-1)
        && checkBST(root->right, root->data+1, max);
}
bool checkBST(Node* root) {
    return checkBST(root, INT_MIN, INT_MAX);
}

关于c++ - 测试树是否为二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51731541/

上一篇：algorithm - 鸡蛋掉落谜题中的递归

下一篇：java - LSD基数排序为负整数，无队列

相关文章：

c++ - str.insert 在 VS (c++) 中不起作用

algorithm - 以编程方式获得具有 3 个变量和给定条件的最高结果公式

以优于 O(n^2) 的时间复杂度构造 count 数组

c - C语言中的红黑树

c++ - 这个代码块到底是如何工作的[树]？

c++ - 使用 boost::signals2::signal 作为处理程序时出错

c++ - 如何在 SymbolicC++ 中输入符号变量

c++ - std::strings 的容量()、保留()和调整大小()函数

linux - linux 负载计算中的权重是如何选择的？

javascript - 带有 JavaScript 的树在 Internet Explorer 7 上无法正常工作