最近公共祖先节点
【问题描述】
给定一个二叉树（共n个节点），求其中k个节点的最近公共祖先节点。每个节点只有左右孩子指针，没有父指针。
【解法思路一】
（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的节点即是待求的最近公共祖先节点，其实路径是惟一的，很快找到
沿着得分为k的孩子往一找，直到孩子得分都小于k,返回父亲
【解法思路三】 对二的简化
（1）遍历二叉树,找到一个待求的结点，则将根结点到待求结点的得分加1 ，用一个栈即可实现
（2）从根节点向下查找最深的得分为k的节点即是待求的最近公共祖先节点。其实路径是惟一的，很快找到
沿着得分为k的孩子往一找，直到孩子得分都小于k,返回父亲
阅读(4095) | 评论(0) | 转发(0) |
