find lca(lowest common ancestry) in a binary tree

2014-11-30 02:42:38

Author: lipeng  Like(0)  View Comment(0)

  1. public static Tree findLca(Tree tree, MyInteger lcaNum, int node1, int node2){
  2.         if(tree==null){
  3.             return null;
  4.         }
  5.         MyInteger lLca = new MyInteger(0);
  6.         Tree ltree = findLca(tree.left, lLca, node1, node2);
  7.         if(lLca.i==2){
  8.             lcaNum.i=2;
  9.             return ltree;
  10.         }
  11.         MyInteger rLca = new MyInteger(0);
  12.         Tree rtree = findLca(tree.right, rLca, node1, node2);
  13.         if(rLca.i==2){
  14.             lcaNum.i=2;
  15.             return rtree;
  16.         }
  17.         int selfLca = 0;
  18.         if(node1==tree.value||node2==tree.value){
  19.             selfLca = 1;
  20.         }
  21.         lcaNum.i = lLca.i + rLca.i + selfLca;
  22.         return tree;
  23. }
  24.  
  25. public class MyInteger{
  26.     public int i = 0;
  27.     public MyInteger(int i){
  28.         this.i = i;
  29.     }
  30.     public String toString(){
  31.         return String.valueOf(i);
  32.     }
  33. }

  
Back