学步园

75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int  m_nvalue;
TreeNode*  m_pLeft;
TreeNode*  m_pRight;
}; 
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

/*
75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int  m_nvalue;
TreeNode*  m_pLeft;
TreeNode*  m_pRight;
}; 
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

对于一个子树的根结点来说，如果那两个结点分别位于该子树的左右子树，则最低共同父结点为该子树的根结点，
如果那两个结点都位于该子树的左子树，则最低共同父结点位于该子树根结点的左子树，
否则来自右子树。递归
*/

//寻找二叉树两个结点的最低共同父节点
TreeNode *FindFirstCommonParentNode(TreeNode *pRoot, TreeNode *pNodeOne, TreeNode *pNodeTwo)
{
    if (NULL==pRoot)
    {
        return NULL;
    }
    if (pRoot==pNodeOne || pRoot==pNodeTwo)
    {
        return pRoot;
    }
    TreeNode *pLeft = FindFirstCommonParentNode(pRoot->m_pLeft, pNodeOne, pNodeTwo);
    TreeNode *pRight = FindFirstCommonParentNode(pRoot->m_pRight, pNodeOne, pNodeTwo);

    if (NULL==pLeft) //1、左子树没有找到任何一个结点，则第一个公共父节点必定在右子树，而且找到第一个结点就是最低共同父节点
    {
        return pRight;
    }
    else if (NULL==pRight) //2、右子树没有找到任何一个结点，则第一个公共父节点必定在左子树，而且找到第一个结点就是最低共同父节点
    {
        return pLeft;
    }
    else          //3、分别在结点的左右子树找到，则此节点必为第一个公共父节点
    {
        return pRoot;
    }
}