一个算法题
作者：tyc611.cublog.cn，2008-09-30
【问题描述】
给定一个二叉树（共n个节点），求其中k（k >= 2）个节点的最近公共祖先节点。每个节点只有左右孩子指针，没有父指针。
【解法思路一】
（1）遍历二叉树，对每个节点给出从根节点到每个节点的路径编码（左孩子为0，右孩子为1），时间复杂度O(n)；
（2）比较这k个节点的路径，找出最长的公共前缀路径，时间复杂度O(k*h)（其中，h从根节点到待求的最近公共祖先节点的路径长度）；
（3）按照找到的公共前缀路径，从根节点向下查找，最后找到的节点即为待求的最近公共祖先节点，时间复杂度度为O(h)。
【解法思路二】
（1）递归处理，对每棵子树进行打分（=左子树得分+右子树得分+当前节点得分）。如果当前节点是目标节点之一，则得分为1；否则得分为0。如果遇到一棵子树的得分为k，即可放弃对另一棵子树的处理。时间复杂度O(n*k)或O(n*logk)或O(n)。
（2）从根节点向下查找最深的得分为k的节点即是待求的最近公共祖先节点。
上面的这两种方法是比较常用的方法，对于类似问题也有较好的效果。
阅读(1275) | 评论(0) | 转发(0) |
