7.2 案例二：（面试题68）树中两个节点的最低公共祖先

面试官：前面两轮面试下来感觉怎么样？

应聘者：感觉还好，只是大脑连续转了两个小时，有点累。

面试官：面试是一个体力活，是挺累的。不过程序员这个行当本身也是体力活，没有好的身体还真撑不住。面试中也要看看你们的体力怎么样。

应聘者：（笑笑并点点头）说得有道理。

面试官：开个玩笑。现在可以开始面试了吧？

应聘者：好的，我准备好了。

面试官：请简要介绍一下你最近的一个项目。

应聘者：我最近完成的项目是Civil 3D（一款基于AutoCAD的土木设计软件）中的Multi-Target。这个Target指的是道路的边缘。之前道路的边缘只能是Civil中的一个数据类型，叫Alignment，我的工作是让Civil支持其他类型的数据作为道路的边缘，如AutoCAD中的Polyline等。

面试官：有没有考虑到以后有可能添加新的数据类型作为道路的边缘？

应聘者：这在开发的过程中就发生过。在第二版的需求文档中添加了一种叫作Pipeline的道路边缘。由于我的设计中考虑了扩展性，最后只要添加新的class就行了，几乎不需要对已有的代码进行任何修改。

面试官：你是怎么做到的？

应聘者在白纸上用UML画了一张类型关系图（图略）。

应聘者：（指着图解释）从这张图中可以看出，一旦需要支持新的道路边缘，如Pipeline，我们只需继承出新的class就可以了，对已有的其他class没有影响。

面试官心理：

对自己的工作讲得很细致、很深入，这个项目的确是你设计和实现的。可以看出，你对面向对象的设计和开发有着较深的理解。

面试官：（点点头）的确是这样的。接下来我们做一道编程题吧。我的题目是输入两个树节点，求它们的最低公共祖先。

应聘者：这棵树是不是二叉树？

面试官：是又怎么样，不是又怎么样？

应聘者：如果是二叉树，并且是二叉搜索树，那么是可以找到公共节点的。

面试官：那假设是二叉搜索树，你怎么查找呢？

应聘者：（有些激动，说得很快）二叉搜索树是排序过的，位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大，我们只需要从树的根节点开始和两个输入的节点进行比较。如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子节点。如果当前节点的值比两个节点的值都小，那么最低的共同父节点一定在当前节点的右子树中，于是下一步遍历当前节点的右子节点。这样，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低的公共祖先。

面试官：看起来你对这道题目很熟悉，是不是以前做过啊？

应聘者：（面露尴尬）这个……碰巧……

面试官：（笑）那咱们把题目稍微换一下。如果这棵树不是二叉搜索树，甚至连二叉树都不是，而只是普通的树，又该怎么办呢？

应聘者：（停下来想了十几秒）树的节点中有没有指向父节点的指针？

面试官心理：

反应挺快的，而且提的问题针对性很强。你的沟通能力不错。

面试官：为什么需要指向父节点的指针？

应聘者在白纸上画了一张图，如图7.1所示。

图7.1 树中的节点有指向父节点的指针，用虚线箭头表示

应聘者：（指着自己画的图7.1解释）如果树中的每个节点（除根节点之外）都有一个指向父节点的指针，那么这个问题可以转换成求两个链表的第一个公共节点。假设树节点中指向父节点的指针是pParent，那么从树的每个叶节点开始都有一个由指针pParent串起来的链表，这些链表的尾指针都是树的根节点。输入两个节点，那么这两个节点位于两个链表上，它们的最低公共祖先刚好就是这两个链表的第一个公共节点。比如输入的两个节点分别为F和H，那么F在链表F->D->B->A上，而H在链表H->E-> B->A上，这两个链表的第一个交点B刚好也是它们的最低公共祖先。

面试官：求两个链表的第一个共同节点这道题目你是不是之前也做过？

应聘者：（摸摸后脑勺，尴尬地笑笑）这个……又被您发现了……

面试官心理：

能够把这道题目转换成求两个链表的第一个公共节点，你的知识迁移能力不错。感觉你对数据结构很熟悉，基本上达到录用标准了。不过我很有兴趣看看你的极限在哪里。再加大点难度试试吧。

面试官：（笑）那只好再把题目的要求改变一下了。现在假设这棵树是普通的树，而且树中的节点没有指向父节点的指针。

应聘者：（稍微流露出一丝抓狂的表情，语气中透出失望）好吧，我再想想。

面试官：这道题目只比前面的两道稍微难一点点，你能搞定的。

应聘者：（静下来思考了两分钟）所谓两个节点的公共祖先，指的是这两个节点都出现在某个节点的子树中。我们可以从根节点开始遍历一棵树，每遍历到一个节点时，判断两个输入节点是不是在它的子树中。如果在子树中，则分别遍历它的所有子节点，并判断两个输入节点是不是在它们的子树中。这样从上到下一直找到的第一个节点，它自己的子树中同时包含两个输入的节点而它的子节点却没有，那么该节点就是最低的公共祖先。

面试官：能不能举个具体的例子说明你的思路？

应聘者：（一边在纸上画图7.2一边解释）假设还是输入节点F和H。我们先判断A的子树中是否同时包含节点F和H，得到的结果为true。接着我们再先后判断A的两个子节点B 和C的子树是不是同时包含F和H， B的结果是true而C的结果是false。接下来我们再判断B的两个子节点D和E，发现这两个节点得到的结果都是false。于是B是最后一个公共祖先，即我们的输出。

图7.2 一棵普通的树，树中的节点没有指向父节点的指针

面试官：听起来不错。很明显，当我们判断以节点A为根的树中是否含有节点F的时候，我们需要对D、E等节点遍历一遍；接下来判断以节点B为根的树中是否含有节点F的时候，我们还是需要对D、E等节点再遍历一遍。这种思路会对同一节点重复遍历很多次。你想想看还有没有更快的算法？

应聘者：（双肘抵住桌子，双手抱住头顶，苦苦思索了两分钟）可以用辅助内存吗？

面试官：你需要多大的辅助内存？

应聘者：我的想法是用两个链表分别保存从根节点到输入的两个节点的路径，然后把问题转换成两个链表的最后公共节点。

面试官：（点头，面露赞许）嗯，具体说说。

应聘者：我们首先得到一条从根节点到树中某一节点的路径，这就要求在遍历的时候有一个辅助内存来保存路径。比如我们用前序遍历的方法来得到从根节点到H的路径的过程是这样的：（1）遍历到A，把A存放到路径中，路径中只有一个节点A；（2）遍历到B，把B存放到路径中，此时路径为A->B；（3）遍历到D，把D存放到路径中，