SEMAN

    今天參加MS2006年度秋季校園招聘會(huì)的筆試第三場，有一個(gè)算法題，求一個(gè)樹種兩個(gè)節(jié)點(diǎn)的最低公共節(jié)點(diǎn)，在網(wǎng)上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
    構(gòu)筑函數(shù)： 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;
}