方法1：递归方法：

（1）如果两个节点分别在根节点的左子树和右子树，则返回根节点
（2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树

bool FindNode(BTree* pRoot, BTree* pNode){	if (pRoot == NULL || pNode == NULL)	{		return false;	}	if (pRoot == pNode)	{		return true;	}	bool found = FindNode(pRoot->m_nLeft, pNode);	if (!found)	{		found = FindNode(pRoot->m_nRight,pNode);	}	return found;}BTree* GetCommentParent(BTree* pRoot, BTree* pNode1, BTree* pNode2){	if (FindNode(pRoot->m_nLeft,pNode1))	{		if (FindNode(pRoot->m_nRight, pNode2))		{			return pRoot;//如果两个节点分别在根节点的左子树和右子树，则返回根节点		}		else//如果两个节点都在左子树，则递归处理左子树		{			return GetCommentParent(pRoot->m_nLeft,pNode1,pNode2);		}	}	else	{		if (FindNode(pRoot->m_nLeft,pNode2))		{			return pRoot;//如果两个节点分别在根节点的左子树和右子树，则返回根节点		}		else//如果两个节点都在右子树，则递归处理右子树		{			return GetCommentParent(pRoot->m_nRight,pNode1,pNode2);		}	}}

方法2：

非递归解法：
先求从根节点到两个节点的路径，然后再比较对应路径的节点就行，最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点

bool GetNodePath(BTree* pRoot, BTree* pNode, list<BTree*> & path){	if (pRoot == pNode)	{		path.push_back(pRoot);		return true;	}	if (pRoot == NULL)	{		return false; 	}	path.push_back(pRoot);	bool found = false;	found = GetNodePath(pRoot->m_nLeft,pNode,path);	if (!found)	{		found = GetNodePath(pRoot->m_nRight,pNode,path);	}	if (!found)	{		path.pop_back();	}	return found;}BTree* GetCommentParent2(BTree* pRoot,BTree* pNode1,BTree* pNode2){	if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)	{		return NULL;	}	list<BTree*> path1;	list<BTree*> path2;	bool bResult1 = GetNodePath(pRoot,pNode1,path1);	bool bResult2 = GetNodePath(pRoot,pNode2,path2);	if (!bResult1 || !bResult2)	{		return NULL;	}	list<BTree*>::const_iterator iter1 = path1.begin();	list<BTree*>::const_iterator iter2 = path2.begin();	BTree* pCommentParent = NULL;	while (iter1 != path1.end() && iter2 != path2.end())	{		if (*iter1 == *iter2)		{			pCommentParent = *iter1;		}				iter1++;		iter2++;	}	return pCommentParent;}

完整测试代码：

// FindCommentParent.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <list>#include <queue>using namespace std;//节点的数据结构class BTree{public:	int       m_nValue;	BTree*    m_nLeft;	BTree*    m_nRight;public:	BTree(int value)	{		m_nValue = http://www.mamicode.com/value;>

 
 
 
 
 
C++算法之  求二叉树两个节点的最低公共节点