首页 > 代码库 > 二叉树两个结点的最低共同父节点

二叉树两个结点的最低共同父节点

 

后序遍历就行。

//寻找二叉树两个结点的最低共同父节点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;    }}

  

二叉树两个结点的最低共同父节点