树中两个结点的最低公共祖先

解法1：分别求根结点到两个结点的路径，求出两条路径的最低公共结点即可

struct BinaryTreeNode{
 int m_nValue;
 BinaryTreeNode *m_pLeft;
 BinaryTreeNode *m_pRight;
};

bool FindPath(BinaryTreeNode *pRoot, BinaryTreeNode *pNode, list<BinaryTreeNode*> &path){
 if(pRoot == NULL)
  return false;
 if(pRoot == pNode){
  path.push_back(pRoot);
  return true;
 }
 path.push_back(pRoot);
 bool found = FindPath(pRoot->m_pLeft, pNode, path);
 if(!found)
  found = FindPath(pRoot->m_pRight, pNode, path);
 if(!found)
  path.pop_back();
 return found;
}

BinaryTreeNode* GetLastCommonParent(BinaryTreeNode *pRoot, BinaryTreeNode *pNode1, BinaryTreeNode *pNode2){
 if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
  return NULL;
 list<BinaryTreeNode*> path1, path2;
 bool result1 = FindPath(pRoot, pNode1, path1);
 bool result2 = FindPath(pRoot, pNode2, path2);
 if(!result1 || !result2)
  return NULL;
 list<BinaryTreeNode*>::const_iterator iter1 = path1.begin();
 list<BinaryTreeNode*>::const_iterator iter2 = path2.begin();
 BinaryTreeNode *pLast = NULL;
 while(iter1 != path1.end() && iter2 != path2.end()){
  if(*iter1 == *iter2)
   pLast = *iter1;
  else
   break;
  ++iter1;
  ++iter2;
 }
 return pLast;
}

解法2：递归探测两个节点是否在根结点的子树中

struct BinaryTreeNode{
 int m_nValue;
 BinaryTreeNode *m_pLeft;
 BinaryTreeNode *m_pRight;
};

bool findNode(BinaryTreeNode *pRoot, BinaryTreeNode *pNode){
 if(pRoot == NULL || pNode == NULL)
  return false;
 if(pRoot == pNode)
  return true;
 bool found = findNode(pRoot->m_pLeft, pNode);
 if(!found)
  found = findNode(pRoot->m_pRight, pNode);
 return found;
}

BinaryTreeNode* GetLastCommonParent(BinaryTreeNode *pRoot, BinaryTreeNode *pNode1, BinaryTreeNode *pNode2){
 if(findNode(pRoot->m_pLeft, pNode1)){
  if(findNode(pRoot->m_pRight, pNode2))
   return pRoot;
  else
   GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);
 }
 else{
  if(findNode(pRoot->m_pLeft, pNode2))
   return pRoot;
  else 
   GetLastCommonParent(pRoot->m_pRight, pNode1, pNode2);
 }
}