雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::


    实际上,用树的后序遍历就可以了。当访问到所求的节点A时,如果这两个节点不在一条线上,则它们必定分别在A的左子树和右子树上,后序遍历到第一个满足这个条件的节点就是所要求的节点A。另外,还必须对这两个节点在一条线上的情况,做特殊处理。

代码:

static bool lca(Node *root, int va, int vb, Node *&result, Node* parrent)
{
  
// left/right 左/右子树是否含有要判断的两节点之一 
  bool left = false, right = false;
  
if (!result && root->left) left = lca(root->left,va,vb,result,root);
  
if (!result && root->right) right = lca(root->right,va,vb,result,root);
  
// mid 当前节点是否是要判断的两节点之一 
  bool mid = false;
  
if (root->data == va || root->data == vb) mid=true;
  
if (!result && int(left + right + mid) == 2{
    
if (mid) result = parrent;
    
else result = root;
  }

  
return left | mid | right ;
}


Node 
*lca(Node *root,int va, int vb)
{
  
if (root == NULL) return NULL;
  Node 
*result = NULL;
  lca(root, va, vb,result, NULL);
  
return result;
}


 

 

posted on 2010-12-02 23:36 flyinghearts 阅读(8654) 评论(11)  编辑 收藏 引用 所属分类: 算法

评论

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-03 11:29 陈梓瀚(vczh)
其实嘛,首先数一下两个结点的深度,然后比较深的那个往上走(深-浅)步,最后同时往上走,肯定会命中最近共同父节点的。如果你把二叉树的所有节点看成N的话,我这个算法只需要lg(N)就可以搞定了。后续遍历显然太慢。  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-03 13:19 姓名不重要吧。。
@陈梓瀚(vczh)
如果这颗树不是满二叉树,是一条链,那复杂度就是O(n)了。。求最近公共祖先LCA有专门的算法,。  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-03 20:50 flyinghearts
@陈梓瀚(vczh)
有父指针当然好办,但有不少情况,为节省空间,节点只有两个指针。
  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-04 22:05 曾涛
我觉得logn-n的复杂度足够了

求a b的最近的父节点,首先求根节点到a的路径字符串,再求根节点到b的路径字符串,不用管树的构造有没有father pointer。  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-09 13:35 flyinghearts
@曾涛
最简单的就是后序遍历。你那样处理, 不仅需要占用大量的额外空间,面且找起来也麻烦。

另外,用专用算法,预处理O(n logn),查询O(1),在查询次数时,比这个算法效率差。
  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-16 23:43 夜风
可以采用给节点加上额外标记的方法(算法概论中有提到):
准备两个数组pre和post,分两个步骤
1.采用后续遍历算法从根节点开始遍历
准备一个全局的计数变量tag,初始值为0
遍历过程中,
访问节点i之前,pre[i] = tag++;
访问节点i之后,post[i] = tag++;

2.对于节点u,v,求出
b=min(pre[u],pre[v]);
e=max(post[u],post[v]);
然后求出一个i,满足
域 [ pre[i],post[i] ] 包含 [ b,e ],且 post[i] - pre[i] 最小
(这个只要从0到n遍历一下就可以求得了)
那这个i就是要求的了
算法复杂度O(n)  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2010-12-24 01:04 酿妹汁
省内存不是这么省的.....话说我遇到这种问题都直接在每个节点里保存一个父节点指针数组一直到根节点.....然后两个节点力的数组比较一下.......好吧我是主张大部分情况下用空间换时间  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。[未登录] 2011-09-20 15:25 gary
请问如何往上走。@陈梓瀚(vczh)
  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2011-10-05 17:03 wzm
前提是你这个二叉树建立的时候是双向的!!!@陈梓瀚(vczh)
  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。[未登录] 2012-08-15 09:03 Chipset
这棵树如果自己实现就加个父指针,从当前节点向上走到根节点,这条路沿路节点做一下标记,然后从第2个节点向上走,第一次遇到曾经标记过的节点就是最近公共祖先,一直走到根节点都没遇到就属于不同的两棵树。

这种考试的题目极少有实用价值。  回复  更多评论
  

# re: 面试题: 找出二叉树上任意两个结点的最近共同父结点。 2014-10-16 14:54 3d
后序遍历到第一个满足这个条件的节点就是所要求的节点A。另外,还必须对这两个节点在一条线上的情况,做特殊处理。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理