程序员面试题精选100题(48)-二叉树两个结点的最低共同父结点

题目：二叉树的结点定义如下：

struct TreeNode
{
    int m_nvalue;
    TreeNode* m_pLeft;
    TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。

第一变种是二叉树是一种特殊的二叉树：查找二叉树。也就是树是排序过的，位于左子树上的结点都比父结点小，而位于右子树的结点都比父结点大。我们只需要从根结点开始和两个结点进行比较。如果当前结点的值比两个结点都大，则最低的共同父结点一定在当前结点的左子树中。如果当前结点的值比两个结点都小，则最低的共同父结点一定在当前结点的右子树中。

第二个变种是树不一定是二叉树，每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发，得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点。

这个题：
从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点

代码写不出见这里：
http://zhedahht.blog.163.com/blog/static/25411174201081263815813/

如果结点中有一个指向父结点的指针，我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表
bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)
{
    if(pHead == pNode)
        return true;
    path.push_back(pHead); //这个寻找的结点在左孩子或者右孩子上，那么他是孩子的父亲
    bool found = false;
    if(pHead->m_pLeft != NULL)
        found = GetNodePath(pHead->m_pLeft, pNode, path);
    if(!found && pHead->m_pRight) //不是左孩子，那么就去右边找
        found = GetNodePath(pHead->m_pRight, pNode, path);
    if(!found) // 既不是左孩子又不是右孩子，就滚出来
        path.pop_back();
    return found;
}