|
在进行这个问题之前，我们需要考虑以下几个问题：
（1）题目告诉我们是树，但是没有告诉我们是一棵怎样的树。这里的树可以分为三种结构。第一种：普通的二叉树；第二种：结点中含有指向父亲结点的指针；第三种：二叉搜索树。
（2）对于不同结构的树，处理的方式是不一样的，时间复杂度也是不一样的，我们需要针对每种结构设计解法。
1. 二叉搜索树
二叉搜索树的左子树比根节点小，右子树的值比根节点大，我们可以根据这个性质来考虑这个问题。
我们可以将两个结点分别和根节点做比较，如果两个结点都比根节点小，则在左子树继续比较，反之，则在右子树中继续比较，直到找到一个结点比根节点大或着等于，一个结点比根节点小，则这个根节点就是最低公共祖先。
代码：
struct BinTreeNode
{
int data;
BinTreeNode* pLeft;
BinTreeNode* pRight;
};
class SortBinTree
{
typedef BinTreeNode TreeNode;
public:
TreeNode* FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{
if (pRoot == NULL)
return NULL;
TreeNode* pCur = pRoot;
if (pNode1->data > pCur->data&&pNode2->data > pCur->data)
return FindLowestCommonAnce(pCur->pRight, pNode1, pNode2);
else if (pNode1->data < pCur->data&&pNode2->data < pCur->data)
return FindLowestCommonAnce(pCur->pLeft, pNode1, pNode2);
else
return pCur;
}
};
2. 含有指向父节点的指针
如果树中含有指向父节点的指针，那么我们可以从最低的叶子结点开始到根节点，看成一条由父节点指向下一个结点的单链表，这样问题就可以转化为求两条单链表的相交结点了。
代码：
template<class T>
struct TreeNode
{
T data;
TreeNode* pLeft;
TreeNode* pRight;
TreeNode* pParent;
};
template<class T>
class ParentTree
{
typedef TreeNode<T> TreeNode;
public:
TreeNode* FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
int count1 = 1;
int count2 = 1;
TreeNode* pCur1 = pNode1;
TreeNode* pCur2 = pNode2;
while (pCur1->pParent != NULL)
{
count1++;
pCur1 = pCur1->pParent;
}
while (pCur2->pParent != NULL)
{
count2++;
pCur2 = pCur2->pParent;
}
int Lengthdif = count1 - count2;
TreeNode* pLong = pNode1;
TreeNode* pShort = pNode2;
if (count1 < count2)
{
pLong = pNode2;
pShort = pNode1;
Lengthdif = count2 - count1;
}
for (int i = 0; i < Lengthdif; i++)
{
pLong = pLong->pParent;
}
while (pLong != NULL&&pShort != NULL&&pLong != pShort)
{
pLong = pLong->pParent;
pShort = pShort->pParent;
}
TreeNode* pFirst = pLong;
return pFirst;
}
};
3. 普通二叉树
普通二叉树相比之下有点难，不过我们可以将第二种方法变换一下，从根节点开始向下遍历，并将遍历到的结点保存在某一容器中，这样就形成了一条到指定结点的路径，然后根据两个结点的路径找相同的结点，这个相同的结点就是最低公共祖先。
代码：
template<class T>
class Tree
{
public:
TreeNode* FindLowestCommonAnce(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);
list<TreeNode*>::const_iterator iterator1 = path1.begin();
list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while (iterator1 != path1.end() && iterator2 != path2.end())
{
if (*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
iterator2++;
}
return pLast;
}
bool GetNodepath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>&path)
{
if (pRoot == pNode)
return true;
path.push_front(pRoot);
bool found = false;
found = GetNodepath(pRoot->pLeft, pNode, path);
if (!found)
found = GetNodepath(pRoot->pRight, pNode, path);
if (!found)
path.pop_front(pRoot);
return found;
}
};
第二种方式：
template<class T>
class Tree
{
typedef TreeNode<T> TreeNode;
public:
TreeNode* FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
if (IsInTheBinaryTree(pRoot->pLeft, pNode&&\
IsInTheBinaryTree(pRoot->pLeft, pNode2))
return FindLowestCommonAnce(pRoot->pLeft, pNode1, pNode2);
else if (IsInTheBinaryTree(pRoot->pRight, pNode&&\
IsInTheBinaryTree(pRoot->pRight, pNode2))
return FindLowestCommonAnce(pRoot->pRight, pNode1, pNode2);
else
return pRoot;
}
bool IsInTheBinaryTree(TreeNode* root,TreeNode* n)
{
if (root == n)
return true;
bool found = IsInTheBinaryTree(root->left, n);
if (!found)
found = IsInTheBinaryTree(root->right, n);
return found;
}
};
| 
转播
