Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
There is the same problem in Leetcode called same tree.
Just do a level order traversal.
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> firstQueue = new LinkedList<TreeNode>();
Queue<TreeNode> secondQueue = new LinkedList<TreeNode>();
firstQueue.add(p);
secondQueue.add(q);
while(!firstQueue.isEmpty() && !secondQueue.isEmpty()){
TreeNode first = firstQueue.poll();
TreeNode second = secondQueue.poll();
if(first == null && second == null){
continue;
}else
if(first == null || second == null){
return false;
}
else{
if(first.val != second.val){
return false;
}
firstQueue.add(first.left);
firstQueue.add(first.right);
secondQueue.add(second.left);
secondQueue.add(second.right);
}
}
return true;
}
}
Here my solution using queue, the idea like iterative dfs.
bool isSameTree (TreeNode * a, TreeNode * b) {
if (a == NULL && b == NULL)
return true;
if (a == NULL || b == NULL)
return false;
queue < TreeNode* > qa;
queue < TreeNode* > qb;
qa.push(a);
qb.push(b);
while (qa.size() != 0) {
TreeNode * first = qa.front(); qa.pop();
TreeNode * second = qb.front(); qb.pop();
if (first -> val != second -> val)
return false;
if (first -> left && !second -> left)
return false;
if (!first -> left && second -> left)
return false;
if (first -> left) {
qa.push(first -> left);
qb.push(second -> left);
}
if (first -> right && !second -> right)
return false;
if (!first -> right && second -> right)
return false;
if (first -> right) {
qa.push(first -> right);
qb.push(second -> right);
}
}
return true;
}
Same data and shape or same data?
For same shape and data the previous solutions are good enough.
But for different data i don't think so, Why?
because, All of you assume that the two tree have the same appearance order.
What if the two tree have the same data but they have different In-order, Pre-order and Pre-order, and yes that may happen since the question talks about Binary Trees not Binary Search Tree.
- Vir Pratap Uttam May 10, 2015