情形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 = value;
leftNode = null;
rightNode = null;
}
}
public static void main(String[] args){
BinaryTreeNode A = new BinaryTreeNode(4);
BinaryTreeNode B = new BinaryTreeNode(2);
BinaryTreeNode C = new BinaryTreeNode(6);
BinaryTreeNode D = new BinaryTreeNode(1);
BinaryTreeNode E = new BinaryTreeNode(3);
BinaryTreeNode F = new BinaryTreeNode(5);
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 = getLowestCommonAncestor(null, A, E, F);
BinaryTreeNode res2 = getLowestCommonAncestor(null, A, D, E);
BinaryTreeNode res3 = getLowestCommonAncestor(null, A, B, D);
System.out.println("The lowest common ancestor of 3 and 5 is " +res1.value);
System.out.println("The lowest common ancestor of 1 and 3 is " +res2.value);
System.out.println("The lowest common ancestor of 1 and 2 is " +res3.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 = value;
parentNode = null;
leftNode = null;
rightNode = null;
}
}
public static NewBinaryTreeNode getLowestCommonAncestor1(NewBinaryTreeNode root,NewBinaryTreeNode node1,NewBinaryTreeNode node2){
if(root == null || node1 == null || node2 == null){
return null;
}
int depth1 = findTheDepthOfTheNode(root, node1, node2);
if(depth1 == -1){
return node2.parentNode;
}
int depth2 = findTheDepthOfTheNode(root, node2, node1);
if(depth2 == -1){
return node1.parentNode;
}
//p指向较深的节点q指向较浅的节点
NewBinaryTreeNode p = depth1 > depth2 ? node1 : node2;
NewBinaryTreeNode q = depth1 > depth2 ? node2 : node1;
int depth = Math.abs(depth1 - depth2);
while(depth > 0){
p = p.parentNode;
depth --;
}
while(p != q){
p = p.parentNode;
q = q.parentNode;
}
return p;
}
//求node1的深度，如果node1和node2在一条路径上，则返回-1，否则返回node1的深度
public static int findTheDepthOfTheNode(NewBinaryTreeNode root,NewBinaryTreeNode node1,NewBinaryTreeNode node2){
int depth = 0;
while(node1.p