Kiểm tra cây nhị phân (không phải BST) có giá trị trùng lặp C++

Kiểm tra cây nhị phân thường (không có tính chất BST) có chứa giá trị trùng lặp không.

Giải thuật (Hashing)

1. Duyệt cây (preorder/inorder/postorder đều được)
2. Với mỗi nút: nếu giá trị đã có trong unordered_set → trả về true
3. Thêm giá trị vào set, đệ quy con trái/phải

Ví dụ minh họa

#include <iostream>
#include <unordered_set>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
};

Node* getNode(int data) {
    Node* n = new Node;
    n->data = data; n->left = n->right = NULL;
    return n;
}

bool hasDuplicateHelper(Node* root, unordered_set<int> &s) {
    if (!root) return false;
    if (s.count(root->data)) 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); // trung lap
    root->left->left = getNode(30);
    
    cout << (hasDuplicate(root) ? "Cay co phan tu trung lap" : "Cay KHONG co phan tu trung lap");
}

Kết quả

Cay co phan tu trung lap