Google Interview Question
Jr. Software EngineersCountry: United States
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode
{
int val;
vector<TreeNode*> children;
TreeNode(int val)
{
this->val = val;
}
};
bool IsMirrorImage(TreeNode* t1, TreeNode* t2)
{
if(t1 == NULL && t2 == NULL)
{
return true;
}
if(t1 == NULL || t2 == NULL)
{
return false;
}
bool isMirrorImage = t1->val == t2->val && (t1->children).size() == (t2->children).size();
int size = (t1->children).size();
for(int i=0; isMirrorImage == true && i < size; i++)
{
isMirrorImage = IsMirrorImage((t1->children)[i], (t2->children)[size-i-1]);
}
return isMirrorImage;
}
int main() {
TreeNode* root1 = new TreeNode(1);
root1->children.push_back(new TreeNode(2));
root1->children.push_back(new TreeNode(3));
TreeNode* root2 = new TreeNode(1);
root2->children.push_back(new TreeNode(3));
root1->children.push_back(new TreeNode(2));
cout<<IsMirrorImage(root1, root2);
}
Do level order traversal. At each level, check if the elements form a palindrome.
- random January 30, 2018