Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1584973
  • 博文数量: 399
  • 博客积分: 8508
  • 博客等级: 中将
  • 技术积分: 5302
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-14 09:28
个人简介

能力强的人善于解决问题,有智慧的人善于绕过问题。 区别很微妙,小心谨慎做后者。

文章分类

全部博文(399)

文章存档

2018年(3)

2017年(1)

2016年(1)

2015年(69)

2013年(14)

2012年(17)

2011年(12)

2010年(189)

2009年(93)

分类: LINUX

2010-09-19 00:31:38

最近公共祖先节点

【问题描述】
给定一个二叉树(共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,返回父亲



阅读(4103) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~