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

darkmode