文档章节

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

一贱书生
 一贱书生
发布于 2016/08/09 11:53
字数 1485
阅读 33
收藏 0
点赞 0
评论 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
博文 722
码字总数 600072
作品 0
HDU 2586 How far away ?

How far away ?Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6309 Accepted Submission(s): 2368 include include include u......

iaccepted ⋅ 2015/01/24 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb ⋅ 05/08 ⋅ 0

剑指Offer学习总结-用两个栈实现队列

剑指Offer学习总结-用两个栈实现队列 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000 ⋅ 01/16 ⋅ 0

飞龙的程序员书单 – 数据结构、算法

入门向 啊哈!算法 这本书真心简洁易懂,dijkstra我是看课本怎么看也看不懂,最后看这本书才懂的。真心推荐。 大话数据结构 工程向 算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Cou...

apachecn_飞龙 ⋅ 2016/01/15 ⋅ 0

排序算法汇总——转载自http://blog.csdn.net/zhanglong_daniel/article/details/52513058

1. 冒泡排序 1.1 算法原理: S1:从待排序序列的起始位置开始,从前往后依次比较各个位置和其后一位置的大小并执行S2。 S2:如果当前位置的值大于其后一位置的值,就把他俩的值交换(完成一次...

biubiubiu! ⋅ 2016/10/09 ⋅ 0

新浪、百度、好未来3offer到手全记录 | 牛客面经

新浪、百度、好未来3offer到手全记录 牛客面经 原创 2017-09-19 牛友 招聘消息汇总 渣渣的秋招之路 附上新浪,百度,好未来面经 作者:offer快到碗里来?。! 来源:牛客网 楼主是本科渣渣,...

公子只识黛玉 ⋅ 04/17 ⋅ 0

备战一线互联网公司Java工程师面试题 (1)

Java重点知识 多线程(线程状态、线程并发,Synchronized与Lock的区别和底层原理,常用的锁及其使用场景和原理, volatile和ThreadLocal解决了什么问题,CAS在Java中的实现 线程池原理和实现...

j4love ⋅ 04/14 ⋅ 0

深入理解 ThreadLocal (这些细节不应忽略)

前言 对于 ThreadLocal 的使用,并不难。但要深入理解 ThreadLocal 的实现方式,需要细细揣摩。写本文前,我在网上看了很多关于 ThreadLocal 的分析,但却感到遗憾,因为很多文章存在着一定误...

徐志毅 ⋅ 04/11 ⋅ 0

scala中的==、equals、eq

scala中equals方法和==是检查值是否相等,而eq方法检查的是引用是否相等。 Scala 的==与Java的有何差别 Java 里的既可以比较基本类型也可以比较引用类型。对于基本类型,Java 的==比较 值比较...

张欢19933 ⋅ 04/27 ⋅ 0

4个Java的常用工具,了解一下吧!

在现如今的互联网时代里,Java无疑是一种极为流行的开发语言,无论是程序界还是整个互联网行业势必带来很大的影响。不管是人才需求还是薪资水平上,Java的发展前景都是很乐观的。 关于Java的...

梦想远方_8e96 ⋅ 06/15 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何使用serverchan微信推送告警

之前实现推送告警信息到微信的方法有如下几种: 1、通过企业公众号实现----收费: 2、通过QQ邮箱,在微信平台上开启收到邮件进行提醒; 3、第三方告警平台API,一般也是收费的; 不过最近看文...

问题终结者 ⋅ 5分钟前 ⋅ 0

TCP的RPC

RPC就是远程方法调用(Remote Process Call ),包含了客户端和服务端,涉及了对象的序列化传输。 1.服务端启动,注册远程调用的类2.客户端发送请求信息包含类、方法、参数的一些信息、序列化传...

Cobbage ⋅ 25分钟前 ⋅ 0

IOS-UI UI初步代码布局添加事件

ISO开发界面,UI是必须学习的一部分,其实很早之前想学来了,一直没有沉下心来学习。看到IOS的代码风格和布局就别扭的不行,跟java代码和android布局比较显得不是那么方便,所以一直到现在。...

京一 ⋅ 35分钟前 ⋅ 0

浅谈OpenDaylight的二次开发

OpenDaylight作为一款开源SDN网络控制器,依托于强大的社区支持以及功能特性,成为了目前主流的SDN网络控制器开发平台。在比较稳定的OpenDaylight Helium版本中,已经为开发者提供了大量的网...

wangxuwei ⋅ 45分钟前 ⋅ 0

API 开发中可选择传递 token 接口遇到的一个坑

在做 API 开发时,不可避免会涉及到登录验证,我使用的是jwt-auth 在登录中会经常遇到一个token过期的问题,在config/jwt.php默认设置中,这个过期时间是一个小时,不过为了安全也可以设置更...

等月人 ⋅ 45分钟前 ⋅ 0

Java NIO之文件处理

程序要操作本地操作系统的一个文件,可以分为以下三个部分: 对文件位置的操作 对文件的操作 对文件内容的操作 其中,对文件内容的操作在 Java NIO之Channel 中已经有了介绍,通过FileChann...

士别三日 ⋅ 50分钟前 ⋅ 0

Maven的pom.xml配置文件详解

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.......

小海bug ⋅ 今天 ⋅ 0

解决httpclient超时设置不生效的问题

最近公司有项目需要通过http调用第三方服务,且第三方服务偶有超时,故需要设置一定的超时时间防止不响应的情况出现。 初始设置如下: [java] view plain copy //超时设置 RequestConfig re...

Mr_Tea伯奕 ⋅ 今天 ⋅ 0

过滤器Filter和拦截器HandlerInterceptor

过滤器 依赖于servlet容器。在实现上基于函数回调,可以对几乎所有请求进行过滤,但是缺点是一个过滤器实例只能在容器初始化时调用一次。使用过滤器的目的是用来做一些过滤操作,获取我们想要...

hutaishi ⋅ 今天 ⋅ 0

Redis入门详解(转)

Redis入门详解 Redis简介 Redis安装 Redis配置 Redis数据类型 Redis功能 持久化 主从复制 事务支持 发布订阅 管道 虚拟内存 Redis性能 Redis部署 Redis应用场景 Redis总结 Redis简介: Redi...

xiaoyaoyoufang ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部