พิจารณาว่าเรามีไบนารีทรี ต้นไม้ไบนารีนี้ไม่ใช่ BST เราต้องตรวจสอบว่าไบนารีทรีมีองค์ประกอบเดียวกันมากกว่าหนึ่งครั้งหรือไม่ เพื่อแก้ปัญหานี้ เราจะใช้การแฮช เราจะสำรวจต้นไม้ที่กำหนด สำหรับแต่ละโหนด เราจะตรวจสอบว่ามีโหนดอยู่ในตารางหรือไม่ หากมีอยู่แล้ว ให้คืนค่าเท็จ หรือเป็นจริง
ตัวอย่าง
#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.
