二叉搜索树从testdome

问题描述：

我写的答案在testdome https://www.testdome.com/for-developers/solve-question/9708 二叉搜索树从testdome

的问题给出一个测试样本是大约二叉搜索树：

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

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

例如，对于下面的树： N1（值：1，左：空，右：空） N2（值：2，左：N1，右：N3） N3（值：3，左：空，右：空）呼叫到包含（N 2，3）应自与N2根树返回true包含数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＃）位置：https://stackoverflow.com/questions/45625016/how-to-find-a-node-implement-method-contains-in-a- binary-search-tree-bst –

答

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

另外：性能测试提示“避免输出或任何不必要的代码” – jcjr

答

噢，这里有一个更好的解决方案。你为什么要使用临时变量？在使用递归时，请记住临时变量确实存储在函数的调用堆栈上，也不要使用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; 
}

二叉搜索树从testdome

相关推荐