文档章节

剑指offer(java):求树中两个结点的最低公共祖先

一贱书生
 一贱书生
发布于 2016/08/09 11:53
字数 1485
阅读 90
收藏 0

题目:

    树中两个节点的最低公共祖先。

最近公共祖先简称LCA(Lowest Common Ancestor),所谓LCA,是当给定一个有根树T时,对于任意两个结点u、v,找到一个离根最远的结点x,使得x同时是u和v的祖先,x 便是u、v的最近公共祖先。

 

思路一:

    输入两个树节点,求他们的最低公共祖先,

——如果是二叉树,而且是二叉搜索树,那么是可以找到公共节点的。

二叉搜索树都是排序过的,位于左子树的节点都比父节点小,而位于右子树上面的节点都比父节点大。

  • 如果当前节点的值比两个结点 的值都大,那么最低的共同的父节点一定是在当前节点的左子树中,于是下一步遍历当前节点的左子节点。
  • 如果当前节点的值比两个结点的值都小,那么最低的共同的父节点一定是在当前节点的右子树中,于是下一步遍历当前节点的右子节点。
  • 这样从上到下,找到的第一个在两个输入结点的值之间的节点,就是最低的公共祖先。

package cglib;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    }

public class List1
{  
    public static TreeNode getLastCommonParent(TreeNode root,TreeNode a,TreeNode b)
    {
            if (root==null || a==null || b==null)
                return null;
            while (root != null) {
                if (root.data > a.data  && root.data  > b.data )
                    root = root.left;
                else if (root.data < a.data && root.data < b.data)
                    root = root.right;
                else
                    return root;
            }
            return null;
    }
    
    public static void main(String args[]){
        TreeNode n1 = new TreeNode();
        TreeNode n2 = new TreeNode();
        TreeNode n3 = new TreeNode();
        TreeNode n4 = new TreeNode();
        TreeNode n5 = new TreeNode();
        TreeNode n6 = new TreeNode();
        TreeNode n7 = new TreeNode();
       
        n1.left=n2;
        n1.right=n3;
        n2.left=n4;
        n2.right=n5;
        n3.left=n6;
        n3.right=n7;
        n1.data=10;
        n2.data=8;
        n3.data=13;
        n4.data=4;
        n5.data=9;
        n6.data=12;
        n7.data=17;
        // 搜索二叉树
        //              10
        //           /       \
        //         8         13
        //        /  \       /     \
        //      4    9  12    17
        System.out.println(n1.data);
        System.out.println(n6.data);
        System.out.println(n7.data);
        TreeNode parent=getLastCommonParent(n1, n6, n7);  
        System.out.println(parent.data);
    }


    }

 

输出:

10
12
17
13

 

思路二:

如果这棵树是普通的树,而且树中结点没有指向父结点的指针,解法如下:

 

思路三:

我们可以用深度优先搜索,从叶子节点向上,标记子树中出现目标节点的情况。如果子树中有目标 节点,标记为那个目标节点,如果没有,标记为null。显然,如果左子树、右子树都有标记,说明就已经找到最小公共祖先了。如果在根节点为p的左右子树中 找p、q的公共祖先,则必定是p本身。

换个角度,可以这么想:如果一个节点左子树有两个目标节点中的一个,右子树没有,那这个节点 肯定不是最小公共祖先。如果一个节点右子树有两个目标节点中的一个,左子树没有,那这个节点肯定也不是最小公共祖先。只有一个节点正好左子树有,右子树也 有的时候,才是最小公共祖先。

 

package cglib;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    }

public class List1
{   
    //两个节点的最低公共祖先,参数为两个节点  
    public static TreeNode getLastCommonParent(TreeNode root,TreeNode a,TreeNode b)
    {
        
            //发现目标节点则通过返回值标记该子树发现了某个目标结点
        //如果在根节点为a的左右子树中找a、b的公共祖先,则必定是a本身。
        //同理,如果在根节点为b的左右子树中找a、b的公共祖先,则必定是b本身。
         if (root == null || root == a || root == b)
             return root;
            //查看左子树中是否有目标结点,没有为null  
         TreeNode left = getLastCommonParent(root.left, a, b);  
            //查看右子树是否有目标节点,没有为null  
         TreeNode right = getLastCommonParent(root.right, a, b);  
            //都不为空,说明左右子树都有目标结点,则公共祖先就是本身  
            if (left != null&&right != null)
                return root;  
            //如果发现了目标节点,则继续向上标记为该目标节点  
            return left == null ? right : left;  
          
    }
    
    public static void main(String args[]){
        TreeNode n1 = new TreeNode();
        TreeNode n2 = new TreeNode();
        TreeNode n3 = new TreeNode();
        TreeNode n4 = new TreeNode();
        TreeNode n5 = new TreeNode();
        TreeNode n6 = new TreeNode();
        TreeNode n7 = new TreeNode();
       
        n1.left=n2;
        n1.right=n3;
        n2.left=n4;
        n2.right=n5;
        n3.left=n6;
        n3.right=n7;
        n1.data=1;
        n2.data=2;
        n3.data=3;
        n4.data=4;
        n5.data=5;
        n6.data=6;
        n7.data=7;
        // 搜索二叉树
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //      4    5 6   7
        System.out.println(n1.data);
        System.out.println(n6.data);
        System.out.println(n7.data);
        TreeNode parent=getLastCommonParent(n1, n6, n7);  
        System.out.println(parent.data);
    }


    }

 

输出:

1
6
7
3

 

以上解法需要对同一个结点重复遍历很多次,效率较低,如果允许使用辅助内存,则可以有效率更高的方法,解法如下:

 

package cglib;

import java.util.Stack;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    }

public class List1
{   
      
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){    
        Stack<TreeNode> stackp = new Stack<TreeNode>();        
        Stack<TreeNode> stackq = new Stack<TreeNode>();    
        getPath(root, p, stackp);        
        getPath(root, q, stackq);    
        return lowestCommonAncestor(stackp, stackq);  
        }    
    private static TreeNode lowestCommonAncestor(Stack<TreeNode> stackp, Stack<TreeNode> stackq)    {    
        TreeNode target = null;        
        while (!stackp.isEmpty() && !stackq.isEmpty() && stackp.peek() == stackq.peek())    
        {        
            target = stackp.peek();        
            stackp.pop();        
            stackq.pop();    
            }        
        return target;    
        }    
    private static boolean getPath(TreeNode root, TreeNode p, Stack<TreeNode> stackp)    {    
        // TODO Auto-generated method stub    
        if (root == null)        
            return false;    
        if (root == p)        
        {            
            stackp.push(root);    
            return true;    
            }        
        else        
        {            
            if (getPath(root.left, p, stackp) || getPath(root.right, p, stackp))
            {                
                stackp.push(root);        
                return true;        
                }        
            }        
        return false;    
        }
    /***
     *
     * 这个代码在实现过程中,是当找到给定节点的时候才将路径依次压入stack中的,
     * 也就是说,两个stack的栈顶都是存放着root节点。
     * 因此,此时就应该找两条路径分离开之前的最后一个节点,
     * 此节点就是所求的最低公共祖先。
     * @param args
     */
    
    public static void main(String args[]){
        TreeNode n1 = new TreeNode();
        TreeNode n2 = new TreeNode();
        TreeNode n3 = new TreeNode();
        TreeNode n4 = new TreeNode();
        TreeNode n5 = new TreeNode();
        TreeNode n6 = new TreeNode();
        TreeNode n7 = new TreeNode();
       
        n1.left=n2;
        n1.right=n3;
        n2.left=n4;
        n2.right=n5;
        n3.left=n6;
        n3.right=n7;
        n1.data=1;
        n2.data=2;
        n3.data=3;
        n4.data=4;
        n5.data=5;
        n6.data=6;
        n7.data=7;
        // 搜索二叉树
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //      4    5 6   7
        System.out.println(n1.data);
        System.out.println(n6.data);
        System.out.println(n7.data);
        TreeNode parent=lowestCommonAncestor(n1, n6, n7);  
        System.out.println(parent.data);
    }


    }

输出:
1
6
7
3

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
今天
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
2018/07/11
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0
给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

我今天查资料时无意发现的,https://github.com/CyC2018/CS-Notes 这个仓库包含了下列几个维度的计算机学习资料: 深受国内程序员喜爱,已经有超过3万多star了。 1. 算法 (1) 剑指 Offer 题解...

JerryWangSAP
2018/10/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HTTP状态码对照表(HTTP response codes)

由于博主工作最近在做大数据日志分析的时候,用到了很多http状态码相关的知识。博主基本只记得其中200和404两个,所以,在此做个笔录。 当浏览者访问一个网页时,浏览者的浏览器会向网页所在...

em_aaron
8分钟前
0
0
java 反射

基本概念 RTTI,即Run-Time Type Identification,运行时类型识别。RTTI能在运行时就能够自动识别每个编译时已知的类型。   要想理解反射的原理,首先要了解什么是类型信息。Java让我们在运...

细节探索者
19分钟前
0
0
推荐转载连接

https://www.cnblogs.com/ysocean/p/7409779.html#_label0

小橙子的曼曼
45分钟前
0
0
雷军亲自打造的套餐了解下:用多少付多少

12月28日消息,小米科技创始人兼CEO雷军微博表示,小米移动任我行套餐方案,原则上就是明明白白消费,用多少付多少,不用不花钱!上网、电话和短信都是一毛钱,上网0.1元/M,电话0.1元/分钟,...

linuxCool
56分钟前
0
0
协议简史:如何学习网络协议?

大学时,学到网络协议的7层模型时,老师教了大家一个顺口溜:物数网传会表应。并说这是重点,年年必考,5分的题目摆在这里,你们爱背不背。 考试的时候,果然遇到这个问题,搜索枯肠,只能想...

Java干货分享
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部