面试题50 树中两个节点的最低公共祖先LCA(Lowest Common Ancestor )

题目是树的最低公共祖先，我们先来考虑树是什么树？

我们从最简单的情况开始分析。

情况一：是二叉树，且是二叉搜索树（二叉排序树，二叉查找树）

分析：由于二叉排序树具有这样的特点：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

所以我们只需要从树的根节点开始和输入的两个节点进行比较。如果当前节点的值比两个节点都大，那么最低公共父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子节点。如果当前节点比两个节点都大，那么最低公共父节点一定在当前节点的右子树中，于是下一步遍历当前节点的右子节点。这样从树中从上到下找到的第一个在输入节点的值之间的节点就是最低公共祖先。

struct node //二叉树节点数据结构
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int );

Node* findLowerstCommonAncestor(Node* root,int value1,int value2)
{
while ( root!= NULL )
{
int value= root->getValue(); //获取当前节点的值
if ( value> value1&& value> value2 ) //当前节点的值大于两输入值
root = root->getLeft();
elseif (value< value1&& value< value2) //当前节点的值校园两输入值
root = root->getRight();
else
return root;
}
return NULL;
}

时间复杂度是树的深度，空间复杂度是O(1)。

情况二：是二叉树，但是普通的二叉树

方法一：一个简单的复杂度为 O(n) 的算法，解决LCA问题

1) 找到从根到n1的路径，并存储在一个向量或数组中。

2)找到从根到n2的路径，并存储在一个向量或数组中。

3) 遍历这两条路径，直到遇到一个不同的节点，则前面的那个即为最低公共祖先.（相当于寻找两个链表上的最后一个公共节点）