Two Mirror Trees
Given a Two Binary Trees, write a function that returns true if one is mirror of other, else returns false.
Example 1:
Input:
T1: 1 T2: 1
/ \ / \
2 3 3 2
Output: 1
Example 2:
Input:
T1: 10 T2: 10
/ \ / \
20 30 20 30
/ \ / \
40 60 40 60
Output: 0
c++ implementation:
void inorder(Node *n, vector<int> &v)
{
if (n->left != NULL)
inorder(n->left, v);
v.push_back(n->data);
if (n->right != NULL)
inorder(n->right, v);
}
int areMirror(Node* a, Node* b)
{
if (a == NULL && b == NULL)
return true;
if (a == NULL || b== NULL)
return false;
vector<int> v1, v2;
inorder(a, v1);
inorder(b, v2);
if (v1.size() != v2.size())
return false;
for (int i=0, j=v2.size()-1; j >= 0;
i++, j--)
if (v1[i] != v2[j])
return false;
return true;
}
time complexity: O(N)
No comments