バイナリツリー（BSTではない）の値がC++で重複していないかどうかを確認します

二分木があると考えてください。この二分木は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.