# SEMAN

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

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 小小

# 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;
}

# 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;
}

# 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;
}  回复  更多评论