1/28/2017

[Interview type questions] First pair non matching leaves

Input: Given two (binary) trees, return the first pair of non-matching leaves Tree 1: A, B, C, D, E, null, null Tree 2: A, D, B
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[] {};
 }
       

1 comment:

  1. Thanks for sharing, nice post! Post really provice useful information!

    Giaonhan247 chuyên dịch vụ vận chuyển hàng đi mỹ mặt hàng nước hoa pháp chính hãng hay dịch vụ cách mua hàng trên ebay việt nam từ dịch vụ mua hàng mỹ cùng với mua hàng trên amazon ship về việt nam uy tín, giá rẻ.

    ReplyDelete