数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装研究
法律研究检查二叉树（非 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.
更新于： 2019 年 10 月 22 日
214 次浏览
广告