剑指offer-第七章面试案例2（树中两个节点的公共祖先节点）

import java.util.LinkedList; import java.util.Queue; import java.util.Stack; //树中两个节点的最低公共祖先 //第一种情况：只是一颗二叉树，而且还是排序二叉树。思路：从根节点开始找起，如果这两个数一个大于 //根节点，一个小于根节点，那么最低公共子节点就是根节点。 //第二种情况：只是一颗普通的树，但是有指向父节点的指针。 //那么就变成 了两个链表求第一个公共节点的情况。 //第三种情况：只是一个普通的树，而且没有指针指向根节点。那么就只能用栈来存放遍历了的节点。找到相同的节点为止。 public class TreeLastCommonParent { public class BiTreeNode{ int m_nValue; BiTreeNode m_pLeft; BiTreeNode m_pRight; BiTreeNode m_pParent; } public BiTreeNode createBiTree(int[] pre,int start,int[] ord,int end,int length){ if(pre.length!=ord.length||pre==null||ord==null||length<=0) return null; int value=pre[start]; BiTreeNode root=new BiTreeNode(); root.m_nValue=value; root.m_pRight=root.m_pLeft=null; if(length==1){ if(pre[start]==ord[end]) return root; else throw new RuntimeException("inVaild put"); } //遍历中序遍历的序列找到根节点 int i=0; while(i<length){ if(ord[end-i]==value) break; i++; } int right=i; int left=length-i-1; if(left>0) root.m_pLeft=createBiTree(pre,start+1,ord,end-i-1,length-i-1); if(right>0) root.m_pRight=createBiTree(pre,start+length-i,ord,end,i); return root; } //该树是二叉树，而且还是排序二叉树。 public BiTreeNode commonParent1(BiTreeNode pHead,BiTreeNode p1,BiTreeNode p2){ if(pHead==null) return null; if(p1.m_nValue<pHead.m_nValue&&p2.m_nValue>pHead.m_nValue ||p2.m_nValue<pHead.m_nValue&&p1.m_nValue>pHead.m_nValue){ return pHead; } else if(p1.m_nValue<pHead.m_nValue&&p2.m_nValue<pHead.m_nValue){ return commonParent1(pHead.m_pLeft,p1,p2); } else return commonParent1(pHead.m_pRight,p1,p2); } //该树有指向父节点的指针 public BiTreeNode commonParent2(BiTreeNode pHead,BiTreeNode p1,BiTreeNode p2){ if(pHead==null) return null; int len1=0; int len2=0; while(p1!=pHead){ len1++; p1=p1.m_pParent; } while(p2!=pHead){ len2++; p2=p2.m_pParent; } int dif=len1-len2; BiTreeNode longest=p1; BiTreeNode shortest=p2; if(dif<0){ dif=len2-len1; longest=p2; shortest=p1; } for(int i=0;i<dif;i++) longest=longest.m_pParent; while(longest!=shortest){ longest=longest.m_pParent; shortest=shortest.m_pParent; } return longest; } //该树没有指向父节点的指针 public BiTreeNode commonParent3(BiTreeNode pHead,BiTreeNode p1,BiTreeNode p2){ if(pHead==null) return null; Queue<BiTreeNode> path1=new LinkedList<BiTreeNode>(); Queue<BiTreeNode> path2=new LinkedList<BiTreeNode>(); Queue<BiTreeNode> longPath=path1; Queue<BiTreeNode> shortPath=path2; BiTreeNode head=pHead; getNodePath(pHead,p1,path1); pHead=head; getNodePath(pHead,p2,path2); int dif=path1.size()-path2.size(); if(dif<0){ dif=path2.size()-path1.size(); longPath=path2; shortPath=path1; } for(int i=0;i<dif;i++){ longPath.remove(); } while(longPath.peek()!=shortPath.peek()) { longPath.remove(); shortPath.remove(); } return longPath.peek(); } public boolean getNodePath(BiTreeNode pHead,BiTreeNode p,Queue<BiTreeNode> path1){ if(pHead==null) return false; if(pHead==p||getNodePath(pHead.m_pLeft,p,path1)|| getNodePath(pHead.m_pRight,p,path1)){ path1.add(pHead); return true; } return false; } public static void main(String[] args){ int[] pre={8,4,3,7,9}; int[] ord={3,4,7,8,9}; TreeLastCommonParent treeLastCommon=new TreeLastCommonParent(); BiTreeNode pHead=treeLastCommon.createBiTree(pre,0,ord,pre.length-1,pre.length); BiTreeNode p1=pHead.m_pLeft.m_pRight; BiTreeNode p2=pHead.m_pLeft.m_pLeft; BiTreeNode pCommon=treeLastCommon.commonParent1(pHead, p1, p2); BiTreeNode pCommon3= treeLastCommon.commonParent3(pHead, p1, p2); System.out.println(pCommon.m_nValue+" "); System.out.println(pCommon3.m_nValue+" "); } }

 

转载于:https://www.cnblogs.com/hupp/p/4780008.html