【以下转载自网络】
首先，题目中没有明确说明节点的结构，所以这里分这两种情况讨论：
1. 二叉树节点具有父指针
在节点具有父指针的情况下，显然此二叉树就可以看成是通过父指针连接的"T"型链表，题目也就转化成查找"T"型链表的第一个公共节点。假设p，q分别为所求的两个节点，则通过遍历一遍可以知道p，q分别到根节点的长度pLen和qLen。这样就知道pLen和qLen之间长度之差，也就知道p、q到它们的第一个公共祖先节点k长度之差L。因为p，q到根节点的路径中都包含k到根节点的路径，所以pLen和qLen之差等于p、q到k的长度之差。然后，让p、q到根节点路径长度大的先向前走L，然后长度小再和大的同时向前遍历，当它们两指向同一个节点时，则那个节点即是所求。
[java] view plaincopyprint?
/**
* 有父指针情况下，查找两个节点的最低公共节点
* @author chosen0ne
* 2011-01-18
*/
class BTree{
private BTNode root;
public BTree(BTNode r){
this.root=r;
}
/**
* 查找两个节点的最低公共祖先节点
* @param p
* @param q
* @return BTNode 最低公共祖先节点，没有找到返回null
*/
public BTNode findLowestAncestor(BTNode p,BTNode q){
if(p==null||q==null)
throw new NullPointerException();
int pLen=0,qLen=0;//p，q两个节点到根节点的路径长度
//计算p到根节点的长度
for(BTNode ancestor=p.parent;ancestor!=null;ancestor=ancestor.parent)
pLen++;
//计算q到根节点的长度
for(BTNode ancestor=q.parent;ancestor!=null;ancestor=ancestor.parent)
qLen++;
//如果p到根节点的长度比q长，则让p前进pLen-qLen
for(;pLen>qLen;pLen--)
p=p.parent;
//如果q到根节点的长度比p长，则让q前进qLen-pLen
for(;qLen>pLen;qLen--)
q=q.parent;
//此时，p和q到根节点的长度相同。假设k是最近的公共节点，则p和q到k的长度相同
//p和q按照相同步长1向前遍历，如果存在公共节点则p和去会同时指向它
while(q!=null&&p!=null&&p!=q){
q=q.parent;
p=p.parent;
}
if(p==q)
return p;
return null;
}
/**
* 测试方法，在t中查找a，b的最低公共祖先节点
* @param t
* @param a
* @param b
*/
private static void test(BTree t, BTNode a, BTNode b){
BTree.BTNode p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先节点是 ："+p.data);
else
System.out.println(a.data+","+b.data+"没有公共祖先节点");
}
public static void main(String[] arg){
/* 构造如下二叉树
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNode g=new BTree.BTNode().data("g");
BTree.BTNode f=new BTree.BTNode().data("f");
BTree.BTNode e=new BTree.BTNode().data("e");
BTree.BTNode d=new BTree.BTNode().data("d");
BTree.BTNode c=new BTree.BTNode().data("c").left(f).right(g);
f.parent(c);
g.parent(c);
BTree.BTNode b=new BTree.BTNode().data("b").left(d).right(e);
d.parent(b);
e.parent(b);
BTree.BTNode a=new BTree.BTNode().data("a").left(b).right(c);
b.parent(a);
c.parent(a);
BTree t=new BTree(a);
test(t,c,f);
}
static class BTNode
{
BTNode left;
BTNode right;
BTNode parent;
T data;
public BTNode(){}
public BTNode(BTNode l,BTNode r,BTNode p,T d){
this.left=l;
this.right=r;
this.parent=p;
this.data=d;
}
BTNode left(BTNode l){
this.left=l;
return this;
}
BTNode right(BTNode r){
this.right=r;
return this;
}
BTNode parent(BTNode p){
this.parent=p;
return this;
}
BTNode data(T d){
this.data=d;
return this;
}
}
}
2.二叉树节点不具有父指针
这种情况下，必须通过遍历查找一个节点的祖先集合，然后比较两个节点的祖先集合就可以找到最低的那个。这里采用后序遍历，并传入一个栈记录该节点的祖先节点。在每次访问一个节点时，先把这个节点压入栈，然后判断该节点是不是要查找的那个节点，如果是返回。接着查找它的左子树和右子树，当要查找的节点在它的左右子树中则返回。然后判断该节点与栈顶节点是否相同，是则弹出栈顶元素。这是因为相同就代表了在访问它的左右子树时没有添加新的节点，也就是说要查找的那个节点不在它的左右子树中，则该节点也就是不是要查找的节点的祖先。
[java] view plaincopyprint?
import java.util.ArrayList;
/**
* 没有父指针情况下，查找两个节点的最低公共节点
* @author chosen0ne
* 2011-01-18
*/
class BTree
{
private BTNode root;
public BTree(BTNode r){
this.root=r;
}
/**
* 查找两个节点的最低公共祖先节点
* @param p
* @param q
* @return BTNode 最低公共祖先节点，没有找到返回null
*/
public BTNode findLowestAncestor(BTNode p,BTNode q){
if(p==null||q==null)
throw new NullPointerException();
ArrayList sp=new ArrayList();
ArrayList sq=new ArrayList();
travalPostOrder(root,p,sp);
travalPostOrder(root,q,sq);
//祖先栈中，以先后顺序存储，所以这里倒序来遍历以便找到最低的那个祖先节点
for(int i=sp.size()-1;i>=0;i--)
for(int j=sq.size()-1;j>=0;j--)
if(sp.get(i)==sq.get(j))
return sp.get(i);
return null;
}
/**
* 后序遍历二叉树，进行节点的搜索，当搜索成功时，将该节点的所有祖先存入栈中
* @param n 遍历的节点
* @param p 欲搜索的节点
* @param stack 存储祖先节点的栈，这里使用ArrayList，因为后续查找最低公共祖先时需要遍历所有元素
* @return boolean 是否搜索到该节点
*/
private boolean travalPostOrder(BTNode n,BTNode p,ArrayList stack){
if(n!=null){
stack.add(n);
if(n==p)
return true;
if(travalPostOrder(n.left,p,stack))
return true;
if(travalPostOrder(n.right,p,stack))
return true;
int lastIndex=stack.size()-1;
//如果搜索完n的左右子树后，栈顶还是n，则代表n不是p的祖先节点，所以将n从栈中删除
if(n==stack.get(lastIndex)){
stack.remove(lastIndex);
}
}
return false;
}
/**
* 测试方法，在t中查找a，b的最低公共祖先节点
* @param t
* @param a
* @param b
*/
private static void test(BTree t, BTNode a, BTNode b){
BTree.BTNode p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先节点是 ："+p.data);
else
System.out.println(a.data+","+b.data+"没有公共祖先节点");
}
public static void main(String[] arg){
/* 构造如下二叉树
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNode g=new BTree.BTNode().data("g");
BTree.BTNode f=new BTree.BTNode().data("f");
BTree.BTNode e=new BTree.BTNode().data("e");
BTree.BTNode d=new BTree.BTNode().data("d");
BTree.BTNode c=new BTree.BTNode().data("c").left(f).right(g);
BTree.BTNode b=new BTree.BTNode().data("b").left(d).right(e);
BTree.BTNode a=new BTree.BTNode().data("a").left(b).right(c);
BTree t=new BTree(a);
test(t,a,b);
}
static class BTNode
{
BTNode left;
BTNode right;
T data;
public BTNode(){}
public BTNode(BTNode l,BTNode r,T d){
this.left=l;
this.right=r;
this.data=d;
}
BTNode left(BTNode l){
this.left=l;
return this;
}
BTNode right(BTNode r){
this.right=r;
return this;
}
BTNode data(T d){
this.data=d;
return this;
}
}
}
在没有父指针时，还可以给每个节点添加一个计数器，在进入一个节点时加1，在退出该节点时减1。访问该节点时，如果要查找的节点在该节点的子树中，则返回。实际上，这和上面的算法思想是一样的，只是实现不同。
这两种算法的时间复杂度都是O(n)，效率不错。没有父指针的情况，空间复杂度也是O(n)。 |
转播
