初学者，关于计算最近的共同祖先的函数求教 - 编程论坛

#2

神月泽夜2017-04-22 22:59

求高手贴下源码和注释，让在下研究研究

#3

九转星河2017-04-23 11:55

先要用并查集来判断是否有血缘关系~然后就是要建立二叉树保存信息~最后求该节点到顶点的高度~

[此贴子已经被作者于2017-4-23 11:58编辑过]

#4

神月泽夜2017-04-23 13:45

回复 3楼九转星河

那个...并查集是什么(@﹏@)~

#5

九转星河2017-04-23 15:02

回复 4楼神月泽夜

我也不知道这样符不符合题意~并查集可以看看这个~里面有详细的解释~~
http://blog.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#6

神月泽夜2017-04-23 16:15

回复 5楼九转星河

看了一下这道题感觉用并查集思想的话就是连个结点一直找父节点知道找到相同结点就结束

#7

九转星河2017-04-23 16:32

回复 6楼神月泽夜

但看楼主一开始打算用二叉树~是不是一定要用树型结构储存呢？~感觉这条题目对于什么是共同祖先太过抽象~但感觉还是和并查集有些联系~~

#8

书生牛犊2017-04-23 20:03

嘿嘿，内容比较多，索性我就写到博客里了。。
mark 一个传送门

http://blog.

如果哪位大大知道这种做法思路原名是什么算法，不妨留言告知我，谢谢！

#9

神月泽夜2017-04-23 20:14

回复 7楼九转星河

题目就是要求用二叉树（捂脸）

#10

神月泽夜2017-04-23 20:23

回复 8楼书生牛犊

在下刚接触树，对于先序中序后序遍历的顺序还不太熟练，不知能否多多给我讲解一下
还有我有个想法
就是利用while循环，当p，q结点不等时，深度深的指向其的父结点，若相同则同时指向父结点，直至指向相同结点，返回该结点，不知这样是否可行。

#11

书生牛犊2017-04-23 20:36

回复 10楼神月泽夜

你的方法有个问题就是通常程序员所建立的二叉树每个结点都只会保存有他的子结点的地址信息，你没办法简单直接获取到他的父节点信息。

如果你想知道它的父节点情况，就应该使用深度优先遍历，先找到这个结点p,然后向上递归输出经过的结点，这个过程叫做“输出结点p到根结点的路径”

那，你看你分别查找pq的路径就得用上两次遍历了，之后还得逐个比较判断寻找最近公共祖先。而我所使用的方法只要一次不完整的遍历就够了。。时空复杂度应该是我的比较低。。
-----------------------------------
我在博客文章中使用“后序遍历”这种说法其实是不对的，准确说应该是“深度优先遍历”。刚刚已经修改了博客。

-----------------------------------
所谓先序遍历、后序遍历、中序遍历，唯一的区别就是输出结点信息的先后次序不一样

程序代码：

void pre(Node T){/*先序*/
if(T){

printf(T);
  pre(T->Left);
  pre(T->Right);

}
}
void Inorder(Node T){/*中序*/
if(T){
  pre(T->Left);

printf(T);
  pre(T->Right);

}
}
void After(Node T){/*后序*/
if(T){
  pre(T->Left);
  pre(T->Right);

printf(T);
}
}

#12

神月泽夜2017-04-23 21:08

回复 11楼书生牛犊

只想着解决问题，忘了考虑数据结构所要求的复杂度了，真是汗颜，谢谢你啦

#13

九转星河2017-04-24 20:28

结合过8楼和11楼的说法明白题目意思了~就是说寻找树的两个子节点的最近父节点~因为通常二叉树每个节点都只有一个入口~回溯搜索时就只有一条路径~所以正常算法的时间复杂度应该为0(n)而不是0(n^2)~是多项式的NP问题~时间复杂度为0(n)的算法有很多~~

第一种就是8楼所说的算法~实现起来最简单~就是记录遍历节点状态~在这里我就先不说了~和下面三种算法时间复杂度同是0(n)~不过还是有一点差距的~差了个常量级~具体会在下面总结~

第二种就是逆树~~另外建立一颗树~不过建立该树的指针是倒过来的~性质有点类似于栈~~记录该节点有没有遍历过~如果没有就在该节点上建立一个栈的节点~~
不过这样建立时就要用一个数组指针来记录根节点来作为入口这样搜索就方便了~

这种逆树搜索实现难度感觉还是有一定的~主要用于广搜时要找到并打印出最小权值的一种状态(所以这有时就是广搜纠结的地方~打印状态数据会是逆序的~所以链表逆序算法就有所应用了)~~~

第三种就是用带指针标记的广搜(实质同第一种差不多~不过就是方法上变化了点)~就是用结构体(元素至少包含两个~一个储存值和一个链表指针~还可以加储存节点下标和搜索深度)队列保存数据(注意出队时不要将元素真正删除~直接移动队头指针就行了~也就是所谓的"假出队"~后面打印输出数据可能要用到)~~然后队尾用一个指针指向队头~遍历完毕检查方法和第一种是一样的~~实质两种方法的储存结构可以等效~不同的是第一种方法是深度游优先搜索~第二种方法是广度优先搜索~~

第四种就是用邻接矩阵或者邻接表标记图的状态~不过矩阵或表所储存建立图的方向是逆序的~其实和上面两种方法实质一样~

前面三种的空间复杂度都是0(n)第四种矩阵的话是0(n^2)邻接表则是0(n)~解释一下原题的二叉树结构逆序后每个顶点就那么一个入口所以表的空间复杂度是0(n)~前四种适用于对已知两个节点的一次搜索~~如果要进行多次比较的话寻找就要从新搜索了~~所以就有了第五种搜索方案

该方案其实就是对前四搜索方案的一种改进~~~

其实算法思想就是floyd算法~~~

计算其共同祖先时可以用按搜索深度进行回溯比对~~
该算法的空间复杂度是0(n^2)时间复杂度和树的相对高度有关~最好是0(n*log(n))~此时该树是完全二叉树~最差是(n^2)~此时该树是程线性结构~

总结一下~
第一种是用树结构求解~
第二种是用栈结构深度搜索求解~
第三种是用队列结构和栈结构广度搜索求解~
第四种是用图的储存结构求解~
第五种是求解任意两个节点之间的~

看上去第一种实现最为方便~但事实上每一次搜索的执行操作是一样的~就算直接给出p和q的地址也不能直接把那个地址为入口~具体原因是存在方向可逆性问题~
第二种和第三种一个是深度搜索~一个是广度搜索~但只是建立数据结构的过程不同~建立后的结构实质是一样的~虽然实现起来比第一种要复杂~但是可以以该地址作为入口沿一条路径回到根节点~第四种也和第二第三种差不多~就是储存数据方式和前两种有些出入~邻接矩阵或者邻接表储存结构每一个节点之间是离散关系~其实没必要去真正建立一张图~因为那图原型就是原题给出的树~遍历该树的过程已经能获取矩阵或表的数据~通过矩阵或表就可以求解了~如果直接用矩阵或表来计算则执行效率和第一种差不多~细化的话如果是矩阵则执行效率还会高一些(上面提及过树逆序后每个节点就那么一个出口~其实用表的话可以用一个一标记其出口的一维数组取代就行了)~第五种适用于多次对于任意两个节点的搜索~生成二维表后每次搜索直接查表就行了~不过消耗空间较大和建表时间较长时肯定的~

至于如何选择就个人决定了~~

[此贴子已经被作者于2017-4-24 20:53编辑过]