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; }
Pingback: Find lca | allenlipeng47()