|
1、如果此二叉树为二叉搜索树，即树中所有结点的左子树的结点都比父结点小，所有结点的右子树都比父结点大
对于此种情况，我们只需从树的根结点开始和输入的两个结点进行比较。如果当前结点的值比两个结点的值都大，那么最低的共同父结点一定是在当前结点的左子树中，于是下一步遍历当前结点的左子结点；如果当前结点的值比两个结点的值都小，那么最低的共同父结点一定是在当前结点的右子树中，于是下一步遍历当前结点的右子结点。这样在树中从上到下找到第一个在输入结点的值之间的结点，就是最低的公共祖先。
struct BSNode
{
int _data;
BSNode* _left;
BSNode* _right;
BSNode(int data = 0) :_data(data), _left(NULL), _right(NULL)
{}
};
BSNode* GetLastCommonParent_1(BSNode* pRoot, BSNode* pNode1, BSNode* pNode2)
{
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
{
return NULL;
}
if (pNode1 == pNode2)
{
return pNode1;
}
BSNode* cur = pRoot;
while (true)
{
if ((cur->_data >= pNode1->_data&&cur->_data<=pNode2->_data) ||
(cur->_data>=pNode2->_data&&cur->_data <= pNode1->_data))
return cur;
else if (cur->_data>pNode1->_data)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
return NULL;
}
2、如果此树是含有父结点的二叉树
对于此种情况，可以转化为求两个链表的第一个公共结点。假设树结点中指向父结点的指针是_parent，那么从树每一结点开始都有一个由_parent串起来的链表，这些链表的尾指针都是根结点。输入两个结点，那么这两个结点位于两个链表上，它们的最低公共祖先刚好就是这两个链表的第一个公共结点。
struct BinTreePar
{
int _data;
BinTreePar* _left;
BinTreePar* _right;
BinTreePar* _parent;
BinTreePar(int data = 0) :_data(data), _left(NULL), _right(NULL), _parent(NULL)
{}
};
//求到根结点的路径长度
int BinLen(BinTreePar* pRoot, BinTreePar* pNode)
{
int count = 0;
BinTreePar* cur = pNode;
while (cur != pRoot)
{
++count;
cur = cur->_parent;
}
return count;
}
BinTreePar* GetLastCommonParent_2(BinTreePar* pRoot, BinTreePar* pNode1, BinTreePar* pNode2)
{
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
{
return NULL;
}
if (pNode1 == pNode2)
{
return pNode1;
}
//类似相交单链表找相遇点
BinTreePar* curA = pNode1;
BinTreePar* curB = pNode2;
//计算到根节点的距离
int lenA = BinLen(pRoot, pNode1);
int lenB = BinLen(pRoot, pNode2);
int subLen = lenA - lenB;
if (subLen > 0)
{
while (subLen--)
{
curA = curA->_parent;
}
}
else if (subLen < 0)
{
while (subLen++)
{
curB = curB->_parent;
}
}
while (curA != curB)
{
curA = curA->_parent;
curB = curB->_parent;
}
return curA;
}
3、此树是普通的二叉树
对于此种情况，我们需找到从根节点到输入的两个的路径，然后有辅助的内存来保存路径，然后再从这两条路径中找出最后一个相同的结点。
#include <list>
struct BinTree
{
int _data;
BinTree* _left;
BinTree* _right;
BinTree(int data = 0) :_data(data), _left(NULL), _right(NULL)
{}
};
//寻找路径
bool FindRoot(BinTree* pRoot, BinTree* pNode, list<BinTree*>& listRoot)
{
if (pRoot == NULL || pNode == NULL)
{
return true;
}
listRoot.push_back(pRoot);
if (pRoot == pNode)
{
return true;
}
if (pRoot->_left)
{
bool ret = FindRoot(pRoot->_left, pNode, listRoot);
if (ret)
{
return true;
}
}
if (pRoot->_right)
{
bool ret = FindRoot(pRoot->_right, pNode, listRoot);
if (ret)
{
return true;
}
}
listRoot.pop_back();
}
BinTree* GetLastCommonParent_3(BinTree* pRoot, BinTree* pNode1, BinTree* pNode2)
{
//找到由根节点到pNode1、pNode2的路径，再找最后一个相同的结点，用list保存路径
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
{
return NULL;
}
if (pNode1 == pNode2)
{
return pNode1;
}
list<BinTree*> listRoot1;
list<BinTree*> listRoot2;
FindRoot(pRoot, pNode1, listRoot1);
FindRoot(pRoot, pNode2, listRoot2);
list<BinTree*>::iterator iteA = listRoot1.begin();
list<BinTree*>::iterator iteB = listRoot2.begin();
BinTree* ret = listRoot1.front();
list<BinTree*>::iterator end = listRoot1.end();
while (iteA != listRoot1.end() && iteB != listRoot2.end() && (*iteA)->_data == (*iteB)->_data)
{
ret = *iteA;
++iteA;
++iteB;
}
return ret;
}
| 
转播
