Output: (E,B)
Example:
Tree1 :
A
/ \
B C
/ \
D E
Tree2 :
A
/ \
D B
Solution:
static class TreeNode {
public TreeNode(char v) { val = v;}
char val;
TreeNode left;
TreeNode right;
}
static class MyIterator {
Stack<TreeNode> stack = new Stack<>();
MyIterator(TreeNode root) {
pullAll(root);
}
void pullAll(TreeNode node) {
while(node != null) {
stack.push(node);
node = node.left;
}
}
public TreeNode next() {
TreeNode next = stack.pop();
if (next.right != null) {
pullAll(next.right);
}
return next;
}
public TreeNode nextLeaf() {
while(hasNext()) {
TreeNode next = next();
if (next.left == null && next.right == null) {
return next;
}
}
return null;
}
boolean hasNext() {
return stack.isEmpty() == false;
}
}
public static void main(String[] args) {
TreeNode root1 = new TreeNode('A');
root1.left = new TreeNode('B');
root1.right = new TreeNode('C');
root1.left.left = new TreeNode('D');
root1.left.right = new TreeNode('E');
TreeNode root2 = new TreeNode('A');
root2.left = new TreeNode('D');
root2.right = new TreeNode('B');
char[] res = findFirstNonMatch(root1, root2);
System.out.println(res);
}
static char[] findFirstNonMatch(TreeNode root1, TreeNode root2) {
MyIterator iter1 = new MyIterator(root1);
MyIterator iter2 = new MyIterator(root2);
while(true) {
TreeNode leaf1 = iter1.nextLeaf();
TreeNode leaf2 = iter2.nextLeaf();
if (leaf1 == null || leaf2 == null) break;
if (leaf1.val != leaf2.val) {
return new char[] {leaf1.val, leaf2.val};
}
}
return new char[] {};
}
