find lca(lowest common ancestry) in a binary tree

By | November 30, 2014
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  
public static Tree findLca(Tree tree, MyInteger lcaNum, int node1, int node2){
   if(tree==null){
      return null;
   }
   MyInteger lLca = new MyInteger(0);
   Tree ltree = findLca(tree.left, lLca, node1, node2);
   if(lLca.i==2){
      lcaNum.i=2;
      return ltree;
   }
   MyInteger rLca = new MyInteger(0);
   Tree rtree = findLca(tree.right, rLca, node1, node2);
   if(rLca.i==2){
      lcaNum.i=2;
      return rtree;
   }
   int selfLca = 0;
   if(node1==tree.value||node2==tree.value){
      selfLca = 1;
   }
   lcaNum.i = lLca.i + rLca.i + selfLca;
   return tree;
}