資料結構
網路
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 次瀏覽
廣告