java-75-二叉树两结点的最低共同父结点
import java.util.LinkedList;import java.util.List;import ljn.help.*;public class BTreeLowestParentOfTwoNodes {public static void main(String[] args) {/* * node data is stored in leverOrder.'0' represents null node. * e.g. * int[] data={1,8,7,9,2,0,0,0,0,4,7}; * the tree is: * 1 / \ 8 7 / \ 9 2 / \ 4 7 */ int[] data={1,8,7,9,2,0,0,0,0,4,7}; Node head=Helper.createTree(data); Node node1=new Node(4); Node node2=new Node(9);//their lowest parent should be 8 LinkedList<Node> path1=new LinkedList<Node>();//should be 1,8,2,4 LinkedList<Node> path2=new LinkedList<Node>();//should be 1,8,9 createPath(head,node1,path1); createPath(head,node2,path2); Node lowestParent=lastCommonNode(path1,path2); System.out.println(lowestParent.getData());}//create a path from BTree's root to the specific nodepublic static boolean createPath(Node head,Node node,LinkedList<Node> path){if(head.getData()==node.getData()){return true;}boolean found=false;path.addLast(head);if(head.getLeft()!=null){found=createPath(head.getLeft(),node,path);}if(!found&&head.getRight()!=null){found=createPath(head.getRight(),node,path);}if(!found){path.removeLast();}return found;}/* * find 'lastCommonNode' of two list and return. * e.g * list1=1,2,3,5 * list2=1,2,3,4 * we return 3 */public static Node lastCommonNode(List<Node> list1,List<Node> list2){Node result=null;int len1=list1.size();int len2=list2.size();if(len1==0||len2==0){return null;}for(int i=0,j=0;i<len1&&j<len2;i++,j++){if(list1.get(i)==list2.get(j)){result=list1.get(i);}}return result;}}