求二叉樹中兩個節點的最低公共祖先節點

直接貼代碼，關於求二叉樹中兩個節點的最低公共祖先節點

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

#include "stdafx.h"
#include <iostream>
#include <list>
using namespace std;

//定義二叉樹的節點
struct BinaryTreeNode
{
  char m_nvalue;
  BinaryTreeNode * m_pleft;
  BinaryTreeNode * m_pright;
};

//創建值為value的節點
BinaryTreeNode * CreateBinaryTreeNode(char value)
{
 BinaryTreeNode * p=new BinaryTreeNode();
 p->m_nvalue=value;
 p->m_pleft=NULL;
 p->m_pright=NULL;
 return p;
}

//設置左孩子
void SetLeftchild(BinaryTreeNode * pRoot,BinaryTreeNode * lchild)
{
    if(pRoot==NULL)
  return;
    pRoot->m_pleft=lchild;
}

//設置右孩子
void SetRightchild(BinaryTreeNode * pRoot,BinaryTreeNode * rchild)
{
 if(pRoot==NULL)
  return;
 pRoot->m_pright=rchild;
}

//保存從根到某節點的路徑(最重要函數)
bool getPath(BinaryTreeNode * pRoot,BinaryTreeNode * pNode,list<BinaryTreeNode *> & List)
{
 if(pRoot==NULL || pNode ==NULL)
  return false;
    if(pRoot==pNode)
 {
  List.push_back(pRoot);
  return true;
 }
 List.push_back(pRoot);
 bool result=getPath(pRoot->m_pleft,pNode,List);
 if(!result)
        result=getPath(pRoot->m_pright,pNode,List);
    if(!result)
      List.pop_back();
 return result;
}

BinaryTreeNode * getCommonParent(BinaryTreeNode * pRoot,BinaryTreeNode * pNode1,BinaryTreeNode * pNode2)
{
  list<BinaryTreeNode *> List1;
  list<BinaryTreeNode *> List2;
  bool result1=getPath(pRoot,pNode1,List1);
  bool result2=getPath(pRoot,pNode2,List2);
  if(result1==false || result2==false)
    return NULL;
  BinaryTreeNode * commonParent=NULL;
  list<BinaryTreeNode *>::iterator ite1=List1.begin();
  list<BinaryTreeNode *>::iterator ite2=List2.begin();
  for(;ite1!=List1.end() && ite2!=List2.end();ite1++,ite2++)
  {
    if(*ite1==*ite2)
      commonParent=*ite1;
  else
  break;
  }
  return commonParent;
}

void printList(list<BinaryTreeNode *> &List)
{
 for(list<BinaryTreeNode *>::iterator ite=List.begin();ite!=List.end();ite++)
 {
    cout<<(*ite)->m_nvalue<<" ";
 }
 cout<<endl;
}

//創建一棵如下所示的二叉樹
//                A
//              /  \
//            B    C
//          /  \
//          D    E
//        /  \  /  \
//      F    G  H  I
//

int _tmain(int argc, _TCHAR* argv[])
{
 
    BinaryTreeNode * pA=CreateBinaryTreeNode('A');
    BinaryTreeNode * pB=CreateBinaryTreeNode('B');
 BinaryTreeNode * pC=CreateBinaryTreeNode('C');
 BinaryTreeNode * pD=CreateBinaryTreeNode('D');
 BinaryTreeNode * pE=CreateBinaryTreeNode('E');
 BinaryTreeNode * pF=CreateBinaryTreeNode('F');
 BinaryTreeNode * pG=CreateBinaryTreeNode('G');
 BinaryTreeNode * pH=CreateBinaryTreeNode('H');
 BinaryTreeNode * pI=CreateBinaryTreeNode('I');
   
 SetLeftchild(pA,pB);
 SetRightchild(pA,pC);
    SetLeftchild(pB,pD);
 SetRightchild(pB,pE);
 SetLeftchild(pD,pF);
 SetRightchild(pD,pG);
 SetLeftchild(pE,pH);
 SetRightchild(pE,pI);
   
 BinaryTreeNode * p=getCommonParent(pA,pD,pF);
 if(p!=NULL)
  cout<<"Common Parent is "<<p->m_nvalue<<endl;
 system("PAUSE");
 return 0;
}