文档章节

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

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

繁著
2018/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...

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

没有更多内容

加载失败,请刷新页面

加载更多

2019-1-16

2019-1-16 星期三 晴转霾 早饭:小面包+鸡蛋糕;午饭:馍+地三鲜;晚饭:; 6:50起床,因为媳妇说可能今天晚上去大雁塔那边吃饭,早上起来后洗了个澡(主要因为头发很油了)。 今天早上天气...

莱菔籽
22分钟前
0
0
localDate、localDateTime、localTime的使用

从前端接受的时候,localDate类型的数据要转换,加 @DateTimeFormat(pattern = "yyyy-MM-dd")

shimmerkaiye
29分钟前
1
0
1.二叉树

概念 二叉树(binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的结构树。通常分支被称为“左子树”和“右子树”,左子树和右子树的位置不能随意颠倒。二叉树的第i层 ...

火拳-艾斯
32分钟前
3
0
java 线程

一、通过实现Runnable接口来创建线程 public class TestThread implements Runnable { public void run() { try { for (int i = 0; i < 10; i++) { ......

朝如青丝暮成雪
37分钟前
1
0
关于eclipse2017 import javax.servlet.jsp.tagext引入错误得问题

在eclipse中: 这个javax.servlet.jsp.tagext属于是tomcat相关jar包找到jsp-api.jar 在tomcat文件夹下边的lib文件夹中就有 如果项目中报错的话 把这个加入到项目中 在myeclipse中: 如下图,...

ZhangLG
52分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部