arentNode != null){
node1 = node1.parentNode;
depth ++;
if(node1 == node2){
return -1;
}
}
return depth;
}
复杂度：由于每个节点的深度最多为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
path1 = new Stack
(); boolean flag1 = getThePathOfTheNode(root, node1,path1); if(!flag1){//树上没有node1节点 return null; } Stack
path2 = new Stack
(); 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
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 = getLowestCommonAncest