【出自WR面试题】
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
对于一棵给定的排序二叉树，求两个结点的共同父结点，例如在下图中，结点1和结点5的共同父结点为3。
分析与解答：
方法一：路径对比法
对于一棵二叉树的两个结点，如果知道了从根结点到这两个结点的路径，就可以很容易地找出它们最近的公共父结点。因此，可以首先分别找出从根结点到这两个结点的路径（例如上图中从根结点到结点1的路径为6-＞3-＞2-＞1，从根结点到结点5的路径为6-＞3-＞5）；然后遍历这两条路径，只要是相等的结点都是它们的父结点，找到最后一个相等的结点即为离它们最近的共同父结点，在这个例子中，结点3就是它们共同的父结点。为了便于理解，这里仍然使用3.2节中构造的二叉树的方法。示例代码如下：
程序的运行结果如下：
1与5的最近公共父结点为3
算法性能分析：
当获取二叉树从根结点root到node结点的路径时，最坏的情况就是把树中所有结点都遍历了一遍，这个操作的时间复杂度为O（N），再分别找出从根结点到两个结点的路径，找它们最近的公共父结点的时间复杂度也为O（N），因此，这种方法的时间复杂度为O（N）。此外，这种方法用栈保存了从根结点到特定结点的路径，在最坏的情况下，这个路径包含了树中所有的结点，因此，空间复杂度也为O（N）。
很显然，这种方法还不够理想。下面介绍另外一种能降低空间复杂度的方法。
方法二：结点编号法
根据3.1节中介绍的性质5，可以把二叉树看成是一棵完全二叉树（不管实际的二叉树是否为完全二叉树，二叉树中的结点都可以按照完全二叉树中对结点编号的方式进行编号），下图为对二叉树中的结点按照完全二叉树中结点的编号方式进行编号后的结果，结点右边的数字为其对应的编号。
根据3.1节性质5可以知道，一个编号为n的结点，它的父亲结点的编号为n/2。假如要求node1与node2的最近的共同父结点，首先把这棵树看成是一棵完全二叉树（不管结点是否存在），分别求得这两个结点的编号n1，n2。然后每次找出n1与n2中较大的值除以2，直到n1==n2为止，此时n1或n2的值对应结点的编号就是它们最近的共同父结点的编号，接着可以根据这个编号信息找到对应的结点，具体方法是通过观察二叉树中结点的编号可以发现：首先把根结点root看成1，求root的左孩子编号的方法为把root对应的编号看成二进制，然后向左移一位，末尾补0，如果是root的右孩子，则末尾补1，因此，通过结点位置的二进制码就可以确定这个结点。例如结点3的编号为2（二进制10），它的左孩子的求解方法为10，向左移一位末尾补0，可以得到二进制100（十进制4），位置为4的结点的值为2。从这个特性可以得出通过结点位置信息获取结点的方法，例如要求位置4的结点，4的二进制码为100，由于1代表根结点，接下来的一个0代表是左子树root.lchild，最后一个0也表示左子树root.lchild.lchild，通过这种方法非常容易根据结点的编号找到对应的结点。实现代码如下：
算法性能分析：(www.xing528.com)
这种方法的时间复杂度也为O（N），与方法一相比，在求解的过程中只用了个别的几个变量，因此，空间复杂度为O（1）。
方法三：后序遍历法
很多与二叉树相关的问题都可以通过对二叉树的遍历方法进行改装而求解。对于本题而言，可以通过对二叉树的后序遍历进行改编而得到。具体思路是：查找结点node1与结点node2的最近共同父结点可以转换为找到一个结点node，使得node1与node2分别位于结点node的左子树或右子树中。例如题目中的图，结点1与结点5的最近共同父结点为结点3，因为结点1位于结点3的左子树上，而结点5位于结点3的右子树上。实现代码如下：
把方法一中的FindParentNode替换为本方法的FindParentNode，可以得到同样的输出结果。
算法性能分析：
这种方法与二叉树的后序遍历方法有着相同的时间复杂度O（N）。
引申：如何计算二叉树中两个结点的距离
【出自TX面试题】
题目描述：
在没有给出父结点的条件下，计算二叉树中两个结点的距离。两个结点之间的距离是从一个结点到达另一个结点所需的最小的边数。例如，给出下面的二叉树：
Dist（4，5）=2，Dist（4，6）=4。
分析与解答：
对于给定的二叉树root，只要能找到两个结点n1与n2最低的公共父结点parent，那么就可以通过下面的公式计算出这两个结点的距离：
Dist（n1，n2）=Dist（root，n1）+Dist（root，n2）-2*Dist（root，parent）
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
