找出二叉树中任意两个节点的最低公共父节点

如图中H和F的最低公共祖先节点就是A

解法1:

遍历出所有叶节点到根节点的路径，得到

ABD

ABEH

ACFI

ACG

可以发现要找出H和F的最低祖先节点只要找到任意一条包含F和任意一条一条H的字符串，找出最大前缀的位置即可

这里找出ABEH和ACFI

最大前缀位置即为A处，所以这里A是最低祖先节点

解法2：

写一个递归算法： find(Node root,Node n1,Node n2)

root 是要开始查找的根节点，n1是要找的第一个节点，n2是要查找的第二个节点

{

if(root == null){     //如果根节点为空肯定找不到n1或者n2，所以返回空

return null;

if(root== n1 || root == n2){  如果根节点就是要找的节点之一，那么返回这个节点

return root;

}

Node pleft = find(root.left,n1,n2);

Node pright = find(root.right,n1,n2);

if(pleft !=null && pright！=null){ //如果左右节点都找到n1或者n2了，那么root节点就是最低根节点

return pright;

}elseif(pleft!=null){ //如果左边查找到了，返回左边的查找结果

returnpleft;

}else (pright = null){

return pright ; //右边查找到的结果

}else{

return null;

}

}

}