Amazon Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
why do you need to call "containsKey" before "remove" ?
"remove" returns null if key is NOT found in map - in such case, you should return "false" and stop checking
I would also use HashSet instead HashMap
I like the overall approach however this will not work in the case where the Second Set is bigger than the First set take this case for example:
First Set:- 1,2,3,4,5
Second Set:- 1,2,3,4,5,6,7,8
Fill map will put all entries from 1-5 into map, and check map will remove all of them from map but 7 and 8 were not present, so ideally it should return false but your program will return true.
Solution:-
When you find some entry not present, return false immediately.
Convert BST to set. And compare 2 sets.
c++, brute force
void makeIntegerArray(Node* node, set<int>& arr) {
if (node == NULL) return;
arr.insert(node->value);
makeIntegerArray(node->left, arr);
makeIntegerArray(node->right, arr);
}
bool haveSameIntegers(Node* a, Node* b) {
set<int> arrA, arrB;
set<int>::iterator itA, itB;
makeIntegerArray(a, arrA);
makeIntegerArray(b, arrB);
if (arrA.size() != arrB.size()) return false;
itA = arrA.begin();
itB = arrB.begin();
while (itA != arrA.end() && itB != arrB.end()) {
if (*itA != *itB) return false;
itA++;
itB++;
}
return true;
}
It is not a BST, its only a BT. The above solution would work correctly for a BST only if you had done an Indorder traversal instead of a preorder because it looks like you are expecting both arrays to be sorted.
@teli.vaibhav, you just need to traverse the tree and add to the set, doesn't matter if it's a BST or not.
If the two sets are identical, then return true, otherwise return false. Simple.
Well.. the Sets sure should have same identical integers.
But I don't see you comparing the Sets, you converted the 2 sets into 2 arrays and compared the 2 arrays element by element sequentially.. It will fail there as the integers in both arrays though the same, wouldn't be the same sequentially.
@telo.vaibhav - he NAMED the set "arr", he did not actually convert them to arrays. He chose a bad name for variables is all.
Convert BT to set. Compare 2 sets.
c++, brute force
void makeIntegerArray(Node* node, set<int>& arr) {
if (node == NULL) return;
arr.insert(node->value);
makeIntegerArray(node->left, arr);
makeIntegerArray(node->right, arr);
}
bool haveSameIntegers(Node* a, Node* b) {
set<int> arrA, arrB;
set<int>::iterator itA, itB;
makeIntegerArray(a, arrA);
makeIntegerArray(b, arrB);
if (arrA.size() != arrB.size()) return false;
itA = arrA.begin();
itB = arrB.begin();
while (itA != arrA.end() && itB != arrB.end()) {
if (*itA != *itB) return false;
itA++;
itB++;
}
return true;
}
Step 1: Do a simple Inorder traversal of the first tree & save each integer in a Map1<Integer value, number of occurrences>
Step 3: Do a simple Inorder traversal of the second tree & save each integer in Map2, also, check whether each integer is present in the Map1 or not.
If not present, we return false right away.
If present, if the number of occurrences is only 1 (value in Map1), we delete the element else we simply decrement the count.
Step 4:
If your Map1 is empty, it means all the elements are present, return true.
If Map1 is not empty, validate the remaining elements are present in Map2. If yes, return true, else false.
Time complexity: O(m+n)
Space Complexity: O(m+n)
c# implementation using Dictionary. Please check and comment.
using System;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
Node root1 = new Node(5);
root1.left = new Node(1);
root1.right = new Node(6);
root1.left.left = new Node(5);
root1.left.right = new Node(4);
root1.right.left = new Node(3);
root1.right.right = new Node(6);
Node root2 = new Node(1);
root2.left = new Node(3);
root2.right = new Node(4);
root2.left.left = new Node(6);
root2.left.right = new Node(5);
if(HaveSameData(root1,root2))
Console.WriteLine("Same Data");
else
Console.WriteLine("Not same Data");
}
static bool HaveSameData(Node root1, Node root2)
{
Dictionary<int,bool> map = new Dictionary<int,bool>();
Traverse(root1, map);
if(!TraverseAndCheck(root2, map))
return false;
foreach(KeyValuePair<int,bool> item in map)
{
if(!item.Value)
return false;
}
return true;
}
static void Traverse(Node root, Dictionary<int,bool> map)
{
if(root == null)
return;
Traverse(root.left, map);
if(map.ContainsKey(root.data))
map[root.data] = false;
else
map.Add(root.data, false);
Traverse(root.right, map);
}
static bool TraverseAndCheck(Node root, Dictionary<int,bool> map)
{
if(root == null)
return true;
if(map.ContainsKey(root.data))
map[root.data] = true;
else
return false;
return TraverseAndCheck(root.right, map) && TraverseAndCheck(root.left, map);
}
}
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int d)
{
data = d;
}
}
1. Take temp array and initialize all elements to -1.
2. Now traversere tree1 and mark all position of all visited elements in array to 1. if number is repeated keep it same as 1.
3. Now traverse tree2 and for all elements decrease the array counter.
4. If array has any of the element to be 1 then both trees has same integers.
In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison
import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestBT {
public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}
Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);
final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));
if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}
}
public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);
}
public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}
public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}
public static void recursive(Node parent, Set<Integer> setValues) {
setValues.add(parent.getValue());
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}
public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}
/**
* Method for filling tree as binary tree
*
* @param values
* - sequence of integer values of binary tree should be as node
* sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {
int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];
if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}
parent.getChildren().add(n);
// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
newParents.addAll(child.getChildren());
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}
public static class Node {
private Integer value;
private List<Node> children;
public Node(Integer value) {
this.value = value;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
}
}
On my PC the output was:
checkAsTreeSet: 3233
checkSimple: 2439
checkAsMixedSet: 1284
the same
So the checkAsMixedSet is faster then all others
In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison
import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestBT {
public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}
Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);
final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));
if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}
}
public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);
}
public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}
public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}
public static void recursive(Node parent, Set<Integer> setValues) {
setValues.add(parent.getValue());
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}
public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}
/**
* Method for filling tree as binary tree
*
* @param values
* - sequence of integer values of binary tree should be as node
* sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {
int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];
if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}
parent.getChildren().add(n);
// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
newParents.addAll(child.getChildren());
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}
public static class Node {
private Integer value;
private List<Node> children;
public Node(Integer value) {
this.value = value;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
}
}
On my PC the output was:
checkAsTreeSet: 3233
checkSimple: 2439
checkAsMixedSet: 1284
the same
In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison
package TEST;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestBT {
public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}
Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);
final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));
if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}
}
public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);
}
public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}
public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}
public static void recursive(Node parent, Set<Integer> setValues) {
setValues.add(parent.getValue());
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}
public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}
/**
* Method for filling tree as binary tree
*
* @param values
* - sequence of integer values of binary tree should be as node
* sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {
int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];
if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}
parent.getChildren().add(n);
// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
newParents.addAll(child.getChildren());
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}
public static class Node {
private Integer value;
private List<Node> children;
public Node(Integer value) {
this.value = value;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
}
}
#include <iostream>
#include <map>
struct Node {
int value;
Node * leftNode;
Node * rightNode;
};
void addMap(std::map<int, bool> * nodeMap, Node * node) {
if (node != nullptr) {
(*nodeMap)[node->value] = true;
addMap(nodeMap, node->leftNode);
addMap(nodeMap, node->rightNode);
}
}
bool checkRepetitiveNumber(std::map<int, bool> * nodeMap, Node * node) {
if (node != nullptr) {
auto search = nodeMap->find(node->value);
if (search == nodeMap->end()) {
return false || checkRepetitiveNumber(nodeMap, node->leftNode) || checkRepetitiveNumber(nodeMap, node->rightNode);
} else {
return true;
}
} else {
return false;
}
}
int main(int argc, const char * argv[]) {
bool isRepetitive;
Node * firstBinaryTree, * secondBinaryTree;
std::map<int, bool> nodeMap;
isRepetitive = false;
firstBinaryTree = new Node{5, nullptr, nullptr};
firstBinaryTree->leftNode = new Node{1, nullptr, nullptr};
firstBinaryTree->rightNode = new Node{6, nullptr, nullptr};
firstBinaryTree->leftNode->leftNode = new Node{5, nullptr, nullptr};
firstBinaryTree->leftNode->rightNode = new Node{4, nullptr, nullptr};
firstBinaryTree->rightNode->leftNode = new Node{3, nullptr, nullptr};
firstBinaryTree->rightNode->rightNode = new Node{6, nullptr, nullptr};
secondBinaryTree = new Node{12, nullptr, nullptr};
secondBinaryTree->leftNode = new Node{33, nullptr, nullptr};
secondBinaryTree->rightNode = new Node{44, nullptr, nullptr};
secondBinaryTree->leftNode->leftNode = new Node{64, nullptr, nullptr};
secondBinaryTree->leftNode->rightNode = new Node{5, nullptr, nullptr};
addMap(&nodeMap, firstBinaryTree);
isRepetitive = checkRepetitiveNumber(&nodeMap, secondBinaryTree);
if (isRepetitive == true) {
std::cout << "There is a repetitive number." << std::endl;
} else {
std::cout << "There isn't a repetitive number." << std::endl;
}
}
The idea is quite simple that it is to use hash table to take all the elements from the first tree and then check if the second tree has exactly same elements as in the hash table. There is no special about the algorithm but I am going to demonstrate how to use recursive (in some sort of function programming sense) functions to implement the solution. Because tree structure is a very good source to understand functional programming particularly in the sense of sub-problem.
Implementation refer to cpluspluslearning-petert.blogspot.co.uk/2015/10/bts-detect-if-two-tree-have-same.html
TEST
void TestCasesOfCheckTwoTreesWithSameElements()
{
const std::vector<int> testInput1 = { 1, 3, 5, 7, 2, 4, 6, 8 };
auto tree1 = ConstructTreeRecursive(testInput1);
assert(tree1 != nullptr);
{
TreeNode<int>* invalid1 = nullptr;
TreeNode<int>* invalid2 = nullptr;
assert(CheckTwoTreesWithSameValues(invalid1, invalid2) == true);
assert(CheckTwoTreesWithSameValues(tree1, invalid2) == false);
assert(CheckTwoTreesWithSameValues(invalid1, tree1) == false);
}
{
const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 1, 5, 2, 4 };
auto tree2 = ConstructTreeRecursive(testInput2);
assert(tree2 != nullptr);
assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
DeleteTree(&tree2);
}
{
const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8 };
auto tree2 = ConstructTreeRecursive(testInput2);
assert(tree2 != nullptr);
assert(CheckTwoTreesWithSameValues(tree1, tree2) == true);
DeleteTree(&tree2);
}
{
const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8, 9 };
auto tree2 = ConstructTreeRecursive(testInput2);
assert(tree2 != nullptr);
assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
DeleteTree(&tree2);
}
DeleteTree(&tree1);
}
1. Traverse two trees and push numbers in hash set. Duplicated numbers are removed in hash set
2. Compare two hash sets: compare (1) their sizes; (2) numbers one by one.
void preorder(TreeNode *root, unordered_set<int> & set){
if(root == NULL)
return;
set.insert(root->val);
preorder(root->left, set);
preorder(root->right, set);
}
bool isIdentical(TreeNode *n1, TreeNode *n2){
unordered_set<int> set1, set2;
preorder(n1, set1);
preorder(n2, set2);
if(set1.size() != set2.size()){
return false;
}
for(unordered_set<int>::iterator it = set1.begin(); it != set1.end(); it++){
if(set2.find(*it) == set2.end()){
return false; // tree2 does not have a number in tree1
}
}
return true;
}
public bool ContainsSameValues(TreeNode root1, TreeNode root2)
{
var values = GetValues(root1);
return HasSameValues(root2, values);
}
private HashSet<int> GetValues(TreeNode root)
{
var values = new HashSet<int>();
GetValues(root, values);
return values;
}
private void GetValues(TreeNode node, HashSet<int> values)
{
if (node == null)
return;
if (!values.Contains(node.Value))
values.Add(node.Value);
GetValues(node.Left, values);
GetValues(node.Right, values);
}
private bool HasSameValues(TreeNode root, HashSet<int> values)
{
var matched = new HashSet<int>();
return HasSameValues(root, values, matched) && values.Count == 0;
}
private bool HasSameValues(TreeNode node, HashSet<int> values, HashSet<int> matched)
{
if (node == null)
return true;
if (!matched.Contains(node.Value))
{
if (!values.Contains(node.Value))
return false;
values.Remove(node.Value);
matched.Add(node.Value);
}
return HasSameValues(node.Left, values, matched) && HasSameValues(node.Right, values, matched);
}
- divm01986 October 02, 2015