首页 文章

来自testdome的二进制搜索树

提问于
浏览 次
0

我正在为testdome中给出的测试样本编写答案https://www.testdome.com/for-developers/solve-question/9708

问题是关于二叉搜索树：

二进制搜索树（BST）是二叉树，其中每个节点的值大于或等于该节点的左子树中的所有节点中的值，并且小于该节点的右子树中的所有节点中的值 .

编写一个函数，检查给定的二叉搜索树是否包含给定值 .

例如，对于以下树：n1（值：1，左：null，右：null）n2（值：2，左：n1，右：n3）n3（值：3，左：null，右：null）对于包含（n2,3）的调用应该返回true，因为在n2处具有root的树包含数字3. enter image description here

我修改了下面的代码，输出看起来运行良好，但测试结果告诉一个失败存在：大树上的性能测试：超出时间限制你能帮助修改我的模式来修复这个失败吗？

#include <stdexcept>
#include <string>
#include <iostream>

class Node
{
public:
Node(int value, Node* left, Node* right)
{
    this->value = value;
    this->left = left;
    this->right = right;
}

int getValue() const
{
    return value;
}

Node* getLeft() const
{
    return left;
}

Node* getRight() const
{
    return right;
}

private:
int value;
Node* left;
Node* right;
};

class BinarySearchTree
{
public:
static bool contains(const Node& root, int value)
{
    Node* tree;
    int val = root.getValue();
    std::cout<<"current node's value is:"<<val<<'\n';

        if (val==value)
        {
            return true;
        }
        else if (val>value)
        {
            tree = root.getLeft();                
            if(tree != NULL)
            {
                std::cout<<"left node's value is:"<<tree->getValue()<<'\n';
                return contains(*tree, value);
            }
            else 
            {
                return false;
            }
        }
        else
        {
            tree = root.getRight();
            if(tree != NULL)
            {
                std::cout<<"right node's value is:"<<tree->getValue()<<'\n';
                return contains(*tree, value);
            }
            else 
            {
                return false;
            }
        }      
    //throw std::logic_error("Waiting to be implemented");
   }   
};

#ifndef RunTests
int main()
{
Node n1(1, NULL, NULL);
Node n3(3, NULL, NULL);
Node n2(2, &n1, &n3);
std::cout << BinarySearchTree::contains(n2, 3);
}
#endif
c++ binary-tree binary-search-tree

2 回答

  • 1

    删除std :: cout会做 . 打印到终端有很大的时间成本 .

    回复于
  • 1

    哦，这是一个更好的解决方案 . 为什么要使用临时变量？使用递归时请记住，临时变量确实存储在函数的调用堆栈中，也不使用print语句 .

    static bool contains(const Node& root, int value)
{
    if(root.getValue() == value){
         return true;
     }
    else if(root.getValue() < value && root.getRight() != NULL){
        return  contains(*(root.getRight()), value);
    }
    else if(root.getLeft() != NULL){
        return contains(*(root.getLeft()), value);
    }
return false;
}
    回复于

相关问题