首页 > 代码库 > 求树中两个节点的最低公共祖先
求树中两个节点的最低公共祖先
情形1:树是搜索二叉树
思路:从树的根节点开始遍历,如果根节点的值大于其中一个节点,小于另外一个节点,则根节点就是最低公共祖先。否则如果根节点的值小于两个节点的值,则递归求根节点的右子树,如果大于两个节点的值则递归求根的左子树。如果根节点正好是其中的一个节点,那么说明这两个节点在一条路径上,所以最低公共祖先则是根节点的父节点
public static BinaryTreeNode getLowestCommonAncestor(BinaryTreeNode rootParent,BinaryTreeNode root,BinaryTreeNode node1,BinaryTreeNode node2){ if(root == null || node1 == null || node2 == null){ return null; } if((root.value - node1.value)*(root.value - node2.value) < 0){ return root; }else if((root.value - node1.value)*(root.value - node2.value) > 0){ BinaryTreeNode newRoot = ((root.value > node1.value) && (root.value > node2.value)) ? root.leftNode : root.rightNode; return getLowestCommonAncestor(root,newRoot, node1, node2); }else{ return rootParent; } }
复杂度:由于递归调用二叉树,所以时间复杂度是O(logn),空间复杂度是O(1)
测试:
public class BinaryTreeNode { public int value; public BinaryTreeNode leftNode; public BinaryTreeNode rightNode; public BinaryTreeNode(int value){ this.value = http://www.mamicode.com/value;>结果:The lowest common ancestor of 3 and5 is 4
The lowest common ancestor of 1 and3 is 2
Thelowest common ancestor of 1 and 2 is 4
情形2:树是普通的二叉树,且树中节点有指向父节点指针思路:两个节点如果在两条路径上,那么类似于“求两个链表的第一个公共节点”的算法题
//含有指向父节点指针的树节点 public class NewBinaryTreeNode { public int value; public NewBinaryTreeNode parentNode; public NewBinaryTreeNode leftNode; public NewBinaryTreeNode rightNode; public NewBinaryTreeNode(int value){ this.value = http://www.mamicode.com/value;>复杂度:由于每个节点的深度最多为logn,所以时间复杂度为O(logn),空间复杂度O(1)
测试:
public static void main(String[] args){ NewBinaryTreeNode A = new NewBinaryTreeNode(1); NewBinaryTreeNode B = new NewBinaryTreeNode(2); NewBinaryTreeNode C = new NewBinaryTreeNode(3); NewBinaryTreeNode D = new NewBinaryTreeNode(4); NewBinaryTreeNode E = new NewBinaryTreeNode(5); NewBinaryTreeNode F = new NewBinaryTreeNode(6); NewBinaryTreeNode G = new NewBinaryTreeNode(7); A.leftNode = B; A.rightNode = C; B.leftNode = D; B.rightNode = E; B.parentNode = A; C.leftNode = F; C.rightNode = G; C.parentNode = A; D.parentNode = B; E.parentNode = B; F.parentNode = C; G.parentNode = C; NewBinaryTreeNode res1 = getLowestCommonAncestor1(A,E,F); NewBinaryTreeNode res2 = getLowestCommonAncestor1(A,D,E); NewBinaryTreeNode res3 = getLowestCommonAncestor1(A,B,D); System.out.println("The lowest common ancestor of 5 and 6 is " +res1.value); System.out.println("The lowest common ancestor of 4 and 5 is " +res2.value); System.out.println("The lowest common ancestor of 2 and 4 is " +res3.value); }结果:The lowest common ancestor of 5 and6 is 1
The lowest common ancestor of 4 and5 is 2
The lowest common ancestor of 2 and4 is 1
情形3:树是普通的二叉树,节点没有指向父节点的指针思路:用栈来实现类似于指向父节点指针的功能
public static BinaryTreeNode getLowestCommonAncestor2(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2){ if(root == null || node1 == null || node2 == null){ return null; } Stack<BinaryTreeNode> path1 = new Stack<BinaryTreeNode>(); boolean flag1 = getThePathOfTheNode(root, node1,path1); if(!flag1){//树上没有node1节点 return null; } Stack<BinaryTreeNode> path2 = new Stack<BinaryTreeNode>(); boolean flag2 = getThePathOfTheNode(root, node2,path2); if(!flag2){//树上没有node2节点 return null; } if(path1.size() > path2.size()){ //让两个路径等长 while(path1.size() != path2.size()){ path1.pop(); } }else{ while(path1.size() != path2.size()){ path2.pop(); } } if(path1.equals(path2)){//当两个节点在一条路径上时 path1.pop(); return path1.pop(); }else{ BinaryTreeNode p = path1.pop(); BinaryTreeNode q = path2.pop(); while(q != p){ p = path1.pop(); q = path2.pop(); } return p; } } //获得根节点到node节点的路径 public static boolean getThePathOfTheNode(BinaryTreeNode root,BinaryTreeNode node,Stack<BinaryTreeNode> path){ path.push(root); if(root == node){ return true; } boolean found = false; if(root.leftNode != null){ found = getThePathOfTheNode(root.leftNode, node, path); } if(!found && root.rightNode != null){ found = getThePathOfTheNode(root.rightNode, node, path); } if(!found){ path.pop(); } return found; }复杂度:获取node节点的路径时间复杂度为O(n),所以总的时间复制度是O(n),空间复杂度是O(logn)测试:
public static void main(String[] args){ BinaryTreeNode A = new BinaryTreeNode(1); BinaryTreeNode B = new BinaryTreeNode(2); BinaryTreeNode C = new BinaryTreeNode(3); BinaryTreeNode D = new BinaryTreeNode(4); BinaryTreeNode E = new BinaryTreeNode(5); BinaryTreeNode F = new BinaryTreeNode(6); BinaryTreeNode G = new BinaryTreeNode(7); A.leftNode = B; A.rightNode = C; B.leftNode = D; B.rightNode = E; C.leftNode = F; C.rightNode = G; BinaryTreeNode res1 = getLowestCommonAncestor2( A, E, F); BinaryTreeNode res2 = getLowestCommonAncestor2( A, D, E); BinaryTreeNode res3 = getLowestCommonAncestor2( A, B, D); System.out.println("The lowest common ancestor of 5 and 6 is " +res1.value); System.out.println("The lowest common ancestor of 4 and 5 is " +res2.value); System.out.println("The lowest common ancestor of 2 and 4 is " +res3.value); }结果:The lowest common ancestor of 5 and6 is 1
The lowest common ancestor of 4 and5 is 2
The lowest common ancestor of 2 and 4 is 1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。