Minh Hoang
BAN USERUsually we use Stack to do iterative InOrder traversal. With 2 binary trees, we certainly have to use at least 2 stacks.
The each tree has its own traversal steps, the order of PUSH a node in the corresponding stack will not be the same. However, in oder to have the same InOrder, the POP from the corresponding stack must be in the same order.
So, we can use a variable to keep track of that. Iteratively traversal Tree1 only if the variable is null and stop every time a Node is poped out of Stack1. Start traversal the Tree2 from there until a Node is poped out, if it's the same as the Node from Tree1, set the variable to null again.
Something like this:
public static boolean check(Node root1, Node root2) {
Stack<Node> stack1 = new Stack<Node>();
Node current1 = root1;
Stack<Node> stack2 = new Stack<Node>();
Node current2 = root2;
Node popedNode = null;
while(true) {
if(popedNode == null) {
if(current1 != null) {
stack1.push(current1);
current1 = current1.left;
} else {
if(!stack1.isEmpty()) {
popedNode = stack1.pop();
current1 = popedNode.right;
} else {
break;
}
}
} else { //popedNode != null, has been assigned above
if(current2 != null) {
stack2.push(current2);
current2 = current2.left;
} else {
if(!stack2.isEmpty()) {
Node n = stack2.pop();
if(n.value == popedNode.value) {
System.out.println(n.value);
popedNode = null; //continue travel Tree1
}
else
return false;
current2 = n.right;
} else {
break;
}
}
}
}
if(!stack1.isEmpty() || stack2.isEmpty())
return false;
return true;
}
- Minh Hoang May 09, 2015