现在的位置: 首页 > 综合 > 正文

淘宝面试题:有一个一亿节点的树,现在已知两个点,找这两个点的共同的祖先。

2018年02月19日 ⁄ 综合 ⁄ 共 260字 ⁄ 字号 评论关闭

如题。

分析:

假设这棵树的每个结点都有n的指针指向n棵子树,可能有的子树为空。

已知的两个结点的关系有两种情况:

一个结点是另一个结点的祖先,这种情况第一个结点是两个结点的共同祖先;

第三个结点是两个结点的共同祖先。

算法

递归遍历每个结点,

如果当前结点是空结点,返回NULL,

如果当前结点等于两个结点中的一个,返回当前结点指针

递归遍历当前结点的所有子树,返回n个结点指针,

如果只有一个指针非NULL,说明两个结点都在那棵子树中,返回那棵子树的指针,

如果有两个指针非NULL,说明当前结点是这两个结点的共同祖先,返回当前结点指针。

抱歉!评论已关闭.