superstar007
BAN USERAnother option
bool IsMirror(node* left, node* right)
{
//LOAD left AND right NODE FROM DISK
if(left->data!=right->date)
return false;
if(left==null)
return true;
return IsMirror(left->right, right->left) && IsMirror(left->left, right->right);
}
bool IsMirror(node* n)
{
IsMirror(n->left, n->right);
}
we can use hash to do it
string hash(node* tree, bool left)
{
if(tree == null)
return goodhashfunction("0");
if(left == true)
return goodhashfunction(hash(tree->left) + hash(tree->right) + tree->data);
else
return goodhashfunction(hash(tree->right) + hash(tree->left) + tree->data);
}
bool ismirror(node* tree)
{
if(hash(tree->left, true) == hash(tree->right, false))
return true;
else
return false;
}
One option is to combine heap (to get top) with hashtable (to find element in heap). That way insert is o(logn) and retrieval is o(1).
- superstar007 July 14, 2011
You do not need to have whole tree in memory - just one node at the time. Just load node when you enter fucntion. To be exact you need (DEPTH OF TREE) x (SIZE OF NODE) memory
- superstar007 March 18, 2012