检查二叉树（非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 << "该树没有重复的元素。";
}输出结果
该树具有重复的元素。
热门推荐
10 对患者生日祝福语简短
11 结婚祝福语简短装备
12 周岁祝福语学生文案简短
13 订婚领证祝福语简短精辟
14 导师获奖祝福语大全简短
15 新婚购房祝福语简短精辟
16 牛年祝福语简短的爱人
17 送芒果的祝福语简短
18 送给学长毕业祝福语简短