如何求二叉树最接近的共同祖先

论坛 期权论坛 期权     
大爱御姐1073   2018-4-26 13:57   4215   2
分享到 :
0 人收藏

2 个回复

正序浏览
3#
zhuogbeios  1级新秀 | 2018-4-30 01:57:39 发帖IP地址来自
2#
amario  3级会员 | 2018-4-30 01:57:38 发帖IP地址来自
【以下转载自网络】
首先,题目中没有明确说明节点的结构,所以这里分这两种情况讨论:

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)。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP