文档章节

设计一个算法,找出二叉树中某两个结点的第一个公共祖先.。不得将额外的结点存储在另外的数据结构中。注意:这不一定是二叉查找树。

一贱书生
 一贱书生
发布于 2016/11/18 13:54
字数 1268
阅读 1042
收藏 0

题目分析:

假设1:这个二叉树是二叉排序树(O(N))

      如果题目中的二叉树是二叉排序树,那么这道题目变的相对简单很多,我们只需要从根节点开始遍历,有以下三种情况发生:

      (1)如果题目给的两个节点的值都大于当前节点,那么继续遍历当前节点的右子树

      (2)如果题目给的两个节点的值都小于当前节点,那么继续遍历当前节点的左子树

      (3)如果当前节点大于其中一个节点而小于其中另外一个节点,那么则返回该节点,该节点便是两个节点的公共                  祖先节点。

假设2:这个二叉树是普通的二叉树,但是存在指向父节点的指针

       由于每个节点存在指向父节点的指针,所以如果给定任意一个节点,便可以找到从该节点到根节点的路径,因此我们可以找到题目中给予的两个节点分别到根节点的路径,因此该题目便变成了求两个单向链表的第一个公共节点。

假设2延伸:求两个单向链表第一个公共节点有两种方法:

      (1)第一种方法是:两个链表如果有 公共节点,那么从第一个公共节点开始往后的所有节点都相同,我们首先遍历两个链表,求出两个链表的长度。然后设定两个指针分别指向这两个单向链表的头结 点,首先让链表较长的指针先移动,直至移动的剩余长度与链表较短的那个链表长度相同为止,这个时候两个指针开始同时移动,直到两个指针指向的节点相同,这 个节点便是这两个单向链表的第一个公共节点。

      (2)第二种方法是:可以设置两个栈,首先分别把两个链表中的节点依次入栈,接下来从两个栈中同时一个一个的将节点弹出,遇到第一对弹出的节点不同时,那么前一次弹出相同的节点便是这两个链表的第一个公共节点。

 

假设3:这个二叉树是普通的二叉树,并且不存在指向父节点的指针

<方法1>:判断子树中是否存在某节点(时间复杂度O(N^2))

          首先建立一个方法判断一棵树中是否存在某个节点,这个比较简单,只需要遍历整棵树,如果存在返回true,如果不存在则返回false。

      接下来的判断过程就相当于二叉排序数的判断过程了,只不过二叉排序树判断一个节点是否在左子树或者右子树中只需要和父节点比较,而普通的树需要遍历整个左子树或者右子树才能实现, 

 

      (1)如果题目给的两个节点都在右子树,那么继续遍历当前节点的右子树

      (2)如果题目给的两个节点都在左子树,那么继续遍历当前节点的左子树

      (3)如果给定的两个节点一个在左子树,一个在右子树,则返回当前节点。

<方法2>:寻找从根节点到子节点的路径

        如果找到从根节点到两个子节点的路径,那么题目就迎刃而解了,可以用栈遍历二叉树,最后找到从根节点到相应节点的路径,类似二叉树的先序非递归遍历一样,先遍历根节点,接着遍历左子树,接着遍历右子树,直到遍历到相应节点为止,这时栈中的元素便是路径元素。

<方法3>:递归遍历

      设根节点为root,两个节点分别为p,q,用前序遍历方法递归遍历整个二叉树,如果只找到p则返回p,如果只找到q则返回q,如果一个节点的左右子树分别找到p,q,则返回该节点,其他情况返回NULL。

 

 

 

 

 

 

/*
*若p为root的子孙,则返回true
*/
boolean covers(TreeNode root,TreeNode p)
{
if(root==null) return false;
if(root== p) return true;
return covers(root.left,p)||covers(root.right,p);
}
    TreeNode commonAncestorHelper(TreeNode root,TreeNode p,TreeNode q)
    {
    if(root==null) return null;
    if(root == p || root == q) return root;
    boolean is_p_on_left=covers(root.left,p);
    boolean is_q_on_left=covers(root.left,q);
    /*
    * 若p和q不在同一边,则返回root
    */
    if(is_p_on_left!=is_q_on_left) return root;
    /*
    * 否则就在同一边,遍访那一边
    */
    TreeNode child_side=is_p_on_left?root.left:root.right;
    return commonAncestorHelper(child_side,p,q);
    }
TreeNode commonAncestor(TreeNode root,TreeNode p,TreeNode q)
{
if(!covers(root,p)||!covers(root,q))//错误检查
{
return false;
}
return commonAncestorHelper(root,p,q);
}

© 著作权归作者所有

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

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

繁著
09/04
0
0
若干数据结构 && 算法面试题【四】(更新ing)

这是我的第三个面试题汇总。 想看之前的内容请移步 http://zhweizhi.blog.51cto.com/10800691/1763237 若干数据结构 && 算法面试题【一】更新完毕 http://zhweizhi.blog.51cto.com/10800691/...

shangluyi
2016/07/08
0
0
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生
2016/04/28
96
0
数据结构学习笔记(树、二叉树)

                       树(一对多的数据结构) 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树种: (1)有且仅有一个特定的称为根(Root)...

希希里之海
2017/05/15
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

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

我没有三颗心脏
07/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【大福利】极客时间专栏返现二维码大汇总

我已经购买了如下专栏,大家通过我的二维码你可以获得一定额度的返现! 然后,再给大家来个福利,只要你通过我的二维码购买,并且关注了【飞鱼说编程】公众号,可以加我微信或者私聊我,我再...

飞鱼说编程
今天
1
0
Spring5对比Spring3.2源码之容器的基本实现

最近看了《Spring源码深度解析》,该书是基于Spring3.2版本的,其中关于第二章容器的基本实现部分,目前spring5的实现方式已有较大改变。 Spring3.2的实现: public void testSimpleLoad(){...

Ilike_Java
今天
1
0
【王阳明心学语录】-001

1.“破山中贼易,破心中贼难。” 2.“夫万事万物之理不外于吾心。” 3.“心即理也。”“心外无理,心外无物,心外无事。” 4.“人心之得其正者即道心;道心之失其正者即人心。” 5.“无...

卯金刀GG
今天
2
0
OSChina 周三乱弹 —— 我们无法成为野兽

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ _刚刚好: 霸王洗发水这波很骚 手机党少年们想听歌,请使劲儿戳(这里) hahahahahahh @嘻酱:居然忘了喝水。 让你喝可乐的话, 你准忘不了...

小小编辑
今天
10
0
vm GC 日志 配置及查看

-XX:+PrintGCDetails 打印 gc 日志 -XX:+PrintTenuringDistribution 监控晋升分布 -XX:+PrintGCTimeStamps 包含时间戳 -XX:+printGCDateStamps 包含时间 -Xloggc:<filename> 可以将数据保存为......

Canaan_
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部