最低公共祖先问题(链表/树)

//两个链表的第一个公共节点：可以利用两个辅助栈实现， 也
//可以遍历链表两次，求节点个数差，长的链表先遍历， 然后同时开始遍历， 找到相同节点
struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
};
ListNode* FirstPublicNode(ListNode* pHead1, ListNode* pHead2){
    if (pHead1 == nullptr || pHead2 == nullptr)
        return nullptr;
    ListNode* pNode1 = pHead1;
    ListNode* pNode2 = pHead2;
    int list1Nodes = 0;
    int list2Nodes = 0;
    while (pNode1 != nullptr){
        pNode1 = pNode1->m_pNext;
        list1Nodes++;
    }
    while (pNode2 != nullptr){
        pNode2 = pNode2->m_pNext;
        list2Nodes++;
    }
    pNode1 = (list1Nodes > list2Nodes) ? pHead1 : pHead2;
    pNode2 = (pNode1 == pHead1) ? pHead2 : pHead2;
    int nodesDiff = abs(list1Nodes - list2Nodes);
    while (nodesDiff--){
        pNode1 = pNode1->m_pNext;
    }
    while (pNode1 != nullptr && pNode2 != nullptr){
        if (pNode1 != pNode2){
            pNode1 = pNode1->m_pNext;
            pNode2 = pNode2->m_pNext;
        }
        else
            return pNode1;
    }
}

//求树当中两个节点的最低公共祖先
//情况一：说明是二叉树， 二叉查找树（排序的二叉树）：那么从树的根节点开始遍历大于两个节点值则遍历左子树，小于则遍历右子树
struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
bool isLeaf(BinaryTreeNode* pNode){
    return (pNode->m_pLeft == nullptr) && (pNode->m_pRight == nullptr);
}
BinaryTreeNode* leastCommonAncestor(BinaryTreeNode* pHead, BinaryTreeNode* pNode1, BinaryTreeNode* pNode2){
    if (pNode1 == nullptr || pNode2 == nullptr || pHead == nullptr)
        return nullptr;
    int value1 = pNode1->m_nValue;
    int value2 = pNode2->m_nValue;
    if (pNode2->m_nValue < pNode1->m_nValue){
        value1 = pNode2->m_nValue;
        value2 = pNode1->m_nValue;
    }
    BinaryTreeNode* pNode = pHead;
    while (!isLeaf(pNode)){
        int value = pNode->m_nValue;
        if (value > value1 && value < value2){
            return pNode;
        }
        else {
            if (value > value2)
                pNode = pNode->m_pLeft;
            else
                pNode = pNode->m_pRight;
        }
    }
    return nullptr;
}
//情况二：说明是任意的树，节点有指向父节点的指针：转换为了求两个链表（两个节点到根节点的链表）第一个公共节点的问题，
struct TreeNode{
    int m_nValue;
    TreeNode* m_pLeft;
    TreeNode* m_pRight;
    TreeNode* m_pParent;
};
TreeNode* leastCommonAncestor(TreeNode* pNode1, TreeNode* pNode2){
    if (pNode1 == nullptr || pNode2 == nullptr)
        return nullptr;
    TreeNode* pListHead1 = pNode1;
    TreeNode* pListHead2 = pNode2;
    int listLen1 = 0;
    int listLen2 = 0;
    while (pListHead1 != nullptr){
        pListHead1 = pListHead1->m_pParent;
        listLen1++;
    }
    while (pListHead2 != nullptr){
        pListHead2 = pListHead2->m_pParent;
        listLen2++;
    }
    pListHead1 = pNode1;
    pListHead2 = pNode2;
    int listLenDiff = listLen1 - listLen2;
    if (listLen1 < listLen2){
        pListHead2 = pNode1;
        pListHead1 = pNode2;
        listLenDiff = listLen2 - listLen1;
    }
    while (listLenDiff--){
        pListHead1 = pListHead1->m_pParent;
    }
    while (pListHead1 != nullptr && pListHead2 != nullptr){
        if (pListHead1 != pListHead2){
            pListHead1 = pListHead1->m_pParent;
            pListHead2 = pListHead2->m_pParent;
        }
        else
            return pListHead1;
    }
    return nullptr;
}

转载于:https://www.cnblogs.com/songdanzju/p/7441985.html