arbre de recherche binaire de testdome

Question

Je vous écris la réponse pour un échantillon de test donné dans testdome https://www.testdome.com/for-developers/solve-question/9708

La question est sur l'arbre de recherche binaire:

arbre de recherche binaire (BST) est un arbre binaire où le la valeur de chaque noeud est plus grande ou égale aux valeurs de tous les noeuds de la sous-arborescence gauche de ce noeud et est plus petite que les valeurs de tous les noeuds de la sous-arborescence droite de ce noeud.

Écrire une fonction qui vérifie si un arbre de recherche binaire donné contient une valeur donnée.

Par exemple, pour l'arbre suivant: n1 (Valeur: 1, Gauche: null, Droite: null) n2 (Valeur: 2, Gauche: n1, Droite: n3) n3 (Valeur: 3, Gauche : null, droit: null) Appel à contient (n2, 3) doit retourner vrai depuis un arbre avec racine à n2 contient le numéro 3. enter image description here

Je modifié le code ci-dessous, la sortie semble bien fonctionner, mais le résultat du test indique qu'un échec existe en tant que: Test de performance sur un grand arbre: dépassement de la limite de temps Pouvez-vous aider à modifier mon mode pour corriger cet échec?

#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 

Answer 1

Supprimer std :: cout fait. L'impression vers le terminal a un coût en temps énorme.

Answer 2

Oh, Une meilleure solution ici. Pourquoi voulez-vous utiliser des variables temporaires? Lors de l'utilisation de la récursivité, rappelez-vous que les variables temporaires sont stockées dans la pile d'appel de la fonction et n'utilisez pas non plus d'instructions 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; 
}