面试题50：树中两个结点的最低公共祖先

题目：输入树的两个结点，求它们的最低公共祖先。

第一种情况：当树是二叉树搜索树的时候

思路：根据二叉搜索树的性质，左子树都比父节点小，右子树结点值都比父节点大，从根节点开始便利二叉树，如果所给的两个结点都比当前结点的值小，则遍历当前结点的左子树，如果两个结点的值都比当前结点的值大就遍历当前结点的右子树，直到找出第一个介于两个结点之间的值就是最低公共祖先。

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

BTNode * FindLCA(BTNode * root,BTNode * node1,BTNode * node2)
{
 if(root==NULL||node1==NULL||node2==NULL)
  return NULL;
 else
 {
  //如果当前结点的值大于两个结点的值，遍历左子树
  if(root->m_nValue>node1->m_nValue && root->m_nValue>node2->m_nValue)
  {
   return FindLCA(root->m_pLeft,node1,node2);
  }//如果当前结点的值小于两个结点的值，遍历右子树
  else if(root->m_nValue<node1->m_nValue && root->m_nValue<node2->m_nValue)
  {
   return FindLCA(root->m_pRight,node1,node2);
  }
  else
  {
   return root;
  }
 }
}

第二种情况：树是一般的二叉树，但是带有指向父节点的指针

思路：如果带有指向父节点的指针，可以将两个结点看着是两个链表的头结点，然后根据求两个链表的第一个公共结点来求。

#include <iostream>
using namespace std;

struct CSNode
{
 int m_nValue;
 CSNode* m_pParent;//指向父节点
 CSNode* m_pFirstChild;//左结点
 CSNode* m_pNextSibling;//右结点
};

//计算链表的长度
int NodeCount(CSNode* pNode)
{
 assert(pNode);
 int nLen = 0;
 while(pNode)
 {
  nLen++;
  pNode = pNode->m_pParent;
 }
 return nLen;
}

//寻找两个链表的公共结点
CSNode* LCA(CSNode*& pFNode,CSNode*& pSNode)
{
 assert(pFNode && pSNode);
 int nDiff = 0;
 int nCountFir = NodeCount(pFNode);
 int nCountSec = NodeCount(pSNode);
 if (nCountFir > nCountSec)
 {
  nDiff = nCountFir - nCountSec;
  while(nDiff)
  {
   pFNode = pFNode->m_pParent;
   nDiff--;
  }
 }
 else
 {
  nDiff = nCountSec - nCountFir;
  while(nDiff)
  {
   pSNode = pSNode->m_pParent;
   nDiff--;
  }
 }
 assert(pSNode && pFNode);
 while(pFNode != pSNode)
 {
  pFNode = pFNode->m_pParent;
  pSNode = pSNode->m_pParent;
 }
 assert(pFNode);
 return pFNode;
}

//传入树的两个结点，查找它们的最低公共祖先
CSNode* FindLCA(CSNode* pRoot,int nFirst,int nSec,CSNode*& pFNode,CSNode*& pSNode)
{
 //先序遍历树，查找这两个结点的位置
 if (!pRoot)
 {
  return NULL;  
 }
 if (pFNode && pSNode)
 {
  return NULL;
 }
 //比较值
 if (pRoot->m_nValue == nFirst)
 {
  pFNode = pRoot;
 }
 if (pRoot->m_nValue == nSec)
 {
  pSNode = pRoot;
 }
 
 if (pFNode && pSNode)
 {
  //两个结点就是两个链表的头结点，查找最低公共祖先
  return LCA(pFNode,pSNode);
 }
 //递归遍历树
 CSNode* pLCALeft = FindLCA(pRoot->m_pFirstChild,nFirst,nSec,pFNode,pSNode);
 CSNode* pLCARight = FindLCA(pRoot->m_pNextSibling,nFirst,nSec,pFNode,pSNode);
 return pLCALeft == NULL ? pLCARight : pLCALeft;
}

代码来源：http://blog.csdn.net/insistgogo/article/details/9934153

第三种情况：既不是二叉搜索树也没有包含指向父节点的指针

思路：首先寻找从根节点到树中某一结点的路径，所以在遍历的时候需要辅助内存来保存路径。

1.首先从根节点开始遍历，遍历A，把A存放到路径中去，路径中只有一个A

2.遍历B，把B也放入路径中，此时路径为A-B

3.遍历D，把D放入路径中，此时路径为A-B-D

4.遍历F，把F存放到路径中，此时路径为A-B-D-F

5.F没有子节点，此路径不可能到达结点H，把F删除，变为A-B-D

6.遍历G，和结点F一样，这条路也不能到达H，所以仍然是A-B-D

7.由于D的所有子节点都已经遍历过，不可能到达H，所以将D也删除，变为A-B

8.遍历E，把E加入路径，变为A-B-E

9.遍历H，到达目标结点，A-B-E就是从根节点到达H所必须经过的路径

10.然后对F求必须经过的路径

11.找出两条路径中最后的公共结点

从根节点开始到输入的两个结点的两条，需要遍历两次树，每遍历一次的时间复杂度是O(n)，得到的两条路径的长度在最差情况时是O(n)，通常情况下两条路径的长度是O(logn)。

#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct TreeNode 
{
    int m_nValue;    
    std::vector<TreeNode*> m_vChildren;   
};

bool GetNodePath(TreeNode *pRoot,TreeNode *pNode, list<TreeNode*> &path)
{
 if (pRoot=pNode)
 {
  return true;
 }
 path.push_back(pRoot);
 bool found=false;
 vector<TreeNode*>::iterator i=pRoot->m_vChildren.begin();
 while(!found&&i<pRoot->m_vChildren.end())
 {
  found=GetNodePath(*i,pNode,path);
  ++i;
 }
 if (!found)
 {
  path.pop_back();
 }
 return found;
}

TreeNode* GetLastCommonNode(const list<TreeNode*>& path1, const list<TreeNode*>& path2)
{
 list<TreeNode*>::const_iterator i1=path1.begin();
 list<TreeNode*>::const_iterator i2=path2.begin();
 TreeNode* pLast=NULL;
 while(i1!=path1.end()&&i2!=path2.end())
 {
  if (*i1==*i2)
  {
   pLast=*iterator;
  }
  i1++;
  i2++;
 }
 return pLast;
}

TreeNode* GetLastCommonParent(TreeNode* pRoot,TreeNode* pNode1,TreeNode* pNode2)
{
 if (pRoot==NULL||pNode1==NULL||pNode2==NULL)
 {
  return NULL;
 }
 list<TreeNode*> path1;
 GetNodePath(pRoot,pNode1,path1);
 list<TreeNode*> path2;
 GetNodePath(pRoot,pNode2,path2);
 return GetLastCommonNode(path1,path2);
}

代码来自： http://m.blog.csdn.net/blog/dgy610927/39081703