文档章节

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

一贱书生
 一贱书生
发布于 2016/08/09 11:53
字数 1485
阅读 58
收藏 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层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

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

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

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

nanchen2251
07/03
0
0
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
07/12
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Centos7安装docker和docker-compose

docker-安装 yum update yum install -y docker-engine docker-compose pip install -U docker-compose...

落叶清风
14分钟前
0
0
7个Python实战项目代码,让你感受下大神是如何起飞的!

关于Python有一句名言:不要重复造轮子。 但是问题有三个: 1、你不知道已经有哪些轮子已经造好了,哪个适合你用。有名有姓的的著名轮子就400多个,更别说没名没姓自己在制造中的轮子。 2、确...

糖宝lsh
15分钟前
0
0
【随记】Maven 与mysql 版本(maven mysql 5.1.38用的最多)

MySQL Connector/J 我的电脑mysql版本为5.7.20-log maven pom.xml 依赖可用5.1.38 pom.xml依赖代码 $加<properties>变量名的实例代码 <properties><!-- data --><mysql-connector-ja......

颖伙虫
17分钟前
0
0
观察者模式

意图: 在对象的内部状态发生变化时,自动通知外部对象进行响应。 构成 被观察者:内部状态有可能被改变,而且又需要通知外部的对象。 观察者:需要对内部状态的改变做出响应的对象。 Java实...

noob_fly
24分钟前
0
0
设计模式之 MVC

MVC 是 模块化思想或者分层思想的实践。 当我们设计一个Web应用的时候,我们的业务流是,读取数据库中的数据,进行逻辑处理,渲染到页面;如果是交互型的页面,那么页面有输入或者事件发生的...

backbye
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部