C++에서 이진 트리(BST 아님)에 중복 값이 ​​있는지 확인

이진 트리가 있다고 가정해 보겠습니다. 이 이진 트리는 BST가 아닙니다. 이진 트리에 동일한 요소가 두 번 이상 포함되어 있는지 확인해야 합니다. 이를 해결하기 위해 해싱을 사용합니다. 주어진 트리를 탐색하고 각 노드에 대해 노드가 테이블에 있는지 여부를 확인하고 이미 있는 경우에는 false를 반환하고 그렇지 않으면 true를 반환합니다.

예시

#include <iostream>
#include <unordered_set>
using namespace std;
class Node {
   public:
   int data;
   Node *left;
   Node *right;
};
Node* getNode(int data){
   Node *newNode = new Node;
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}
bool hasDuplicateHelper(Node *root, unordered_set<int> &s){
   if(root == NULL)
      return false;
   if (s.find(root->data) != s.end())
      return true;
   s.insert(root->data);
   return hasDuplicateHelper(root->left, s) ||  hasDuplicateHelper(root->right, s);
}
bool hasDuplicate(Node *root){
   unordered_set<int> s;
   return hasDuplicateHelper(root, s);
}
int main() {
   Node *root = getNode(10);
   root->left = getNode(20);
   root->right = getNode(20);
   root->left->left = getNode(30);
   if (hasDuplicate(root))
      cout << "The tree has duplicate elements.";
   else
      cout << "The tree has no duplicate elements.";
}

출력

The tree has duplicate elements.