检查二叉树(非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 << "该树具有重复的元素。";
   else
      cout << "该树没有重复的元素。";
}

输出结果

该树具有重复的元素。