题目
二叉树结点的定义如下：
struct node {
int data;
struct node* left;
struct node* right;
};
给定二叉树中的两个结点，输出这两个结点的最低公共祖先结点（LCA）。注意，该二叉树不一定是二叉搜索树。
比如给定的二叉树如下所示，则可以知道结点1和5的最低公共祖先结点为5，结点4和5的最低公共祖先结点为5。
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
解法
1）自顶向下的方法
我们可以从根结点出发，判断当前结点的左右子树是否包含这两个结点。如果左子树包含两个结点，则它们的最低公共祖先结点也一定在左子树中。如果右子树包含两个结点，则它们的最低公共祖先结点也一定在右子树中。如果一个结点在左子树，而另一个结点在右子树中，则当前结点就是它们的最低公共祖先结点。根据该思路写出代码如下，注意这里已经假定p和q是二叉树中的结点。
/*查找二叉树中两个结点最低公共祖先结点*/
struct node* LCA(struct node *root, struct node *p, struct node *q)
{
if (hasNode(root->left, p) && hasNode(root->left, q)) //p和q都在左子树中
return LCA(root->left, p, q);
if (hasNode(root->right, p) && hasNode(root->right, q)) //p和q都在右子树中
return LCA(root->right, p, q);
return root; //p和q一个在左子树，一个在右子树中，直接返回root
}
/*判断root为根的树是否包含结点p*/
bool hasNode(struct node* root, struct node* p)
{
if (!root) return false;
if (root == p)
return true;
return hasNode(root->left, p) || hasNode(root->right, p);
}
由于我们对每个结点都调用了hasNode函数，而该函数类似于遍历二叉树，复杂度为O(N)，所以总的时间复杂度为O(N^2)，我们期望找到一个更好的方法。
2）自底向上的方法
由于自顶向下的方法需要重复遍历结点，使用自底向上的方法可以避免这种情况。
自底向上遍历结点，一旦遇到结点等于p或者q，则将其向上传递给它的父结点。父结点会判断它的左右子树是否都包含其中一个结点，如果是，则父结点一定是这两个节点p和q的LCA，传递父结点到root。如果不是，我们向上传递其中的包含结点p或者q的子结点，或者NULL(如果子结点不包含任何一个)。该方法时间复杂度为O(N)。
typedef struct node Node;
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // 如果p和q位于不同的子树
return L ? L : R; //p和q在相同的子树，或者p和q不在子树中
}
3）公共路径法
还有一个方法就是依次得到从根结点到结点p和q的路径，找出它们路径中的最后一个公共结点即是它们的LCA。该算法在何海涛先生的博客中有详细描述，这里就不赘述，详见http://zhedahht.blog.163.com/blog/static/25411174201081263815813/，该方法复杂度也为O(N)，不过需要额外的空间存储路径，当然第2种方法中递归也是需要栈空间的，不过整体来看第2种方法简洁但是不是很好理解，而公共路径法则更加易懂。
| 
转播
