SEMAN

曾经沧海难为水、除却巫山不是云

C++博客 首页 新随笔 联系 聚合 管理
  9 Posts :: 3 Stories :: 24 Comments :: 0 Trackbacks

    今天参加MS2006年度秋季校园招聘会的笔试第三场,有一个算法题,求一个树种两个节点的最低公共节点,在网上Google了一下,看到原题大致这样的:
      Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.

The function prototype is as follows: int FindLowestCommonAncestor(node* root,int value1,int value)
           20
          /  \
         8    22
       /   \
      4     12
           /  \
         10    14
    构筑函数: struct TreeNode * FindLowestCommonTreeNode(struct node *pNode,)

Struct TreeNode
{
   int Data;
   TreeNode *pLeft, *pRight;
}

FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
{
   if (pRoot==NULL) 
      return NULL;
   if (pRoot==pNode1 && pRoot==pNode2) 
      return pRoot;
   Struct TreeNode *pTemp;
   if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2)) 
      return pTemp;
   if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2)) 
      return pTemp;
   if (FindLowestAncestor(pRoot,pNode1,pNode1) && FindLowestAncestor(pRoot,pNo
de2,pNode2)) return pRoot;

   return NULL;
}

posted on 2005-11-14 02:05 味全每日C++ 阅读(1111) 评论(5)  编辑 收藏 引用

Feedback

# re: MS的笔试题目 2006-10-22 17:18 小小
更多试题,请访问: www.pghome.net/art.html  回复  更多评论
  

# re: MS的笔试题目 2006-12-28 23:23 kgha
FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
{
if (pRoot==NULL)
return NULL;
if (pRoot==pNode1 && pRoot==pNode2)
return pRoot;
Struct TreeNode *pTemp;
if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2))
return pTemp;
if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2))
return pTemp;
if (FindLowestAncestor(pRoot,pNode1,pNode1) && FindLowestAncestor(pRoot,pNo
de2,pNode2)) return pRoot;

return NULL;
}

  回复  更多评论
  

# re: MS的笔试题目 2006-12-28 23:37 kgha

这样太费解了,不如写两个函数直观:
FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
{
if (pRoot==NULL)
return NULL;
if (pRoot==pNode1 && pRoot==pNode2)
return pRoot;
Struct TreeNode *pTemp;
if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2))
return pTemp;
if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2))
return pTemp;
if (FindNode(pRoot,pNode1) && FindLowestAncestor(pRoot,pNo
de2)) return pRoot;
return NULL;
}
struct TreeNode * FindNode(Struct TreeNode *pRoot, Struct TreeNode *pNode)
{
if(pNode在pRoot下)
{
return pRoot;
}
return NULL;
}
因为最后一步仅仅是在pRoot下是否存在pNode1和pNode2,所以还有优化的余地  回复  更多评论
  

# re: MS的笔试题目 2006-12-28 23:41 kgha
这样太费解了,不如写两个函数直观:
FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
{
if (pRoot==NULL)
return NULL;
if (pRoot==pNode1 && pRoot==pNode2)
return pRoot;
Struct TreeNode *pTemp;
if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2))
return pTemp;
if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2))
return pTemp;
if (FindNode(pRoot,pNode1) && FindNode(pRoot,pNo
de2)) return pRoot;
return NULL;
}
struct TreeNode * FindNode(Struct TreeNode *pRoot, Struct TreeNode *pNode)
{
if(pNode在pRoot下)
{
return pRoot;
}
return NULL;
}
因为最后一步仅仅是在pRoot下是否存在pNode1和pNode2,所以还有优化的余地
上面的有点小错误,呵呵  回复  更多评论
  

# re: MS的笔试题目 2008-03-07 17:31 521zheng
其实没有这么麻烦的,
考虑一下二叉查找树的特点,如果两个节点的值都大于或都小于某一个节点的值,就继续遍历下去,否则返回节点的值
int FindLowesCommonNode(root * node , int a, int b)
{
if(a<=node.value && b<=node.value)
return FindLowesCommonNode(node->left, a,b);
if(a>=node.value && b>=node.value)
return FindLowesCommonNode(node->right, a,b);
return root.value;
}  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理