利用前后序遍历求解树中两个节点的最低公共节点

问题：

     求树种任意两个节点的最低公共节点

 

常见的解法是求解节点到根的路径，对路径做比对。参见： http://gaotong1991.iteye.com/blog/2042770

下面来介绍另外一种方法求解。

准备：

1、什么是最低公共节点？

答：https://en.wikipedia.org/wiki/Lowest_common_ancestor

 

2、最低公共节点有哪些方面需要注意？

答：按照两个节点是否存在一个节点（设为A）是以另外一个节点（设为B）为根的子树中，分为两种情况：

是

    意味着A和B在B的一个分支下，返回B即可。

否

    意味着A和B肯定在公共节点的不同分支下，可以按下文的2、3、4步骤处理。

3、如何判断两个节点是否存在一个节点（设为A）是另外一个节点（设为B）的（直接或间接）孩子？

答：如果两个节点在树的前序和后续遍历中出现的顺序相反，则说明存在；反之，不存在。

 

示例数据：

 

测试用例：

     F/H-->B;B/F-->B

步骤：

1、分别输出树的前序（ABDFGEHIJC）和后续遍历结果(FGDHIJEBCA)；

2、如果F、H在前序和后续中的出现顺序相反，则说明F、H存在一个节点在另外一个节点的子树中的情况（例如选择的节点是B和F，F位于以B为根子树中），直接返回前序遍历中较早出现的一个节点，程序退出。

3、对前序遍历结果求出两个节点(F,H)前面的公共节点数组（按正序排列），记为M(ABD)

4、对后续遍历结果求出两个节点(F,H)后面的公共节点（按逆序排列），记为N(ACBEJI)

5、求M，N的最大公共子序列K(AB)，K的最后一个元素B就是最低公共祖先，程序退出。

特点：

1、前序遍历和后续遍历的结果对于任何两个节点而言都是可用的，意味着不管是对哪两个节点来说，都可以使用遍历的结果；

2、将非线性问题转换为线性问题——最大公共子序列。

评论

1 楼 comsci 2014-09-07  

嘿嘿.......有前途