How to find the lowest common ancestor in a tree 最近公共祖先

[题目]

求二叉树的任意两个节点的最近公共祖先。

此题有多个扩展问题:

  1. 如果只查询一次,二叉树给出向上(parent)链接和不给向上链接时分别有什么解法,最佳空间时间复杂度是多少?
  2. 如果一次性给出多组查询,解法能有什么改进,空间时间复杂度又是什么?

Example

1 / \ 2 3 / \ \ 4 5 6

对于左侧二叉树, 节点 4 , 5的最近公共祖先是2,节点5,6的最近公共祖先是1

[澄清]

在面试中,面试者一般不直接告诉你树是否有向上链接,能否自定义树的node,而这类信息对此题的解法复杂度又有相当重要的影响,面试时应该主动向面试者提出。

[思路]

对于第一问:如果有向上链接,我们只要先求出给定的两点p1, p2分别到root的距离,以及他们的插值(假设为d)。然后将距离较长的点(假设为p1)沿树向上行走直d步。最后将p1 和 p2 同时向上走直到他们相遇。显然,此次相遇是他们第一次相遇,而相遇时所在的节点也就是最近公共的祖先节点。

如果没有向上链接,我们只能通过遍历树的方法来的到最近公共祖先。可以证明,在一棵树中,最近公共祖先必然是1)p1,p2节点中的一个,或者2)p1,p2分别在其左右子树中。通过后序遍历整棵树,分别判断如上的条件即可得到结果。

如上两种情况,最坏情况下,都需要遍历整棵树,所以时间复杂度都是O(n);空间复杂度对于树的遍历都是O(1)。

.....

本文分享自微信公众号 - 包子铺里聊IT(baozitraining)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2014-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

35710
来自专栏tkokof 的技术,小趣及杂念

数学小记之数系

自然数即非负整数(包括 0 和 正整数),字母表示为 N(Natural number) :

21340
来自专栏我的技术专栏

数据结构图文解析之:二叉堆详解及C++模板实现

20550
来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

39060
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

45470
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

38080
来自专栏朱慕之的博客

基础算法

0.创建类 BinaryTreeNode 1.创建方法:传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法,将根节点的左...

7910
来自专栏mini188

多用多学之Java中的Set,List,Map

        很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了。ArrayList是用于实现动态数组...

22850
来自专栏ACM算法日常

算法合集 | 神奇的笛卡尔树 - HDU 1506

笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看...

48220
来自专栏mathor

线性表(一)

12820

扫码关注云+社区

领取腾讯云代金券