對該問題,分為如下幾種情形討論:

情形一:

假如該樹為二叉樹,并且是二叉搜索樹, 依據二叉搜索樹是排過序的, 我們只需要從樹的根結點開始,逐級往下,和兩個輸入的結點進行比較.

如果當前結點的值比兩個結點的值都大,那么最低的公共祖先一定在當前結點的左子樹中,下一步遍歷當前結點的左子節點.

如果當前結點的值比兩個結點的值都小,那么最低的公共祖先一定在當前結點的右子樹中,下一步遍歷當前結點的右子結點.

這樣在樹中從上到下找到的第一個在兩個輸入結點的值之間的結點,就是最低的公共祖先.

情形二:

如果是一棵普通的樹,但是樹的結點(除根結點外)中有指向父結點的指針:

這個問題可以轉換為求兩個鏈表的第一個公共結點.

假設樹結點中指向父結點的指針是pParent,那么從樹的每一個葉結點開始都一個由指針pParent串起來的鏈表,這些鏈表的尾指針都是樹的根結點.

輸入兩個結點,這兩個結點位于兩個鏈表上,它們的最低公共祖先剛好是這兩個鏈表的第一個公共結點. 比如輸入的兩個結點分別為F和H,那么F在鏈表F->D->B->A上,?

而H在鏈表H->E->B->A上, 這兩個鏈表的第一個交點B 剛好也是它們的最低公共祖先.參見下面的圖示

情形三:

僅是一棵普通的樹,沒有其它條件:

求出從根結點到指定結點的路徑,這樣我們就得到兩條路徑,比較這兩條路徑的最低公共祖先就可以了.

具體的思路還是,從樹的根節點開始遍歷,參見下面的圖,?

假設還是輸入結點F和H, 我們先判斷A的子樹中是否同時包含結點F和H, 得到的結果為true,接著我們再先后判斷A的兩個子結點B和C的子樹是否同時包含F和H,結果是B的結果為true而C的結果是false, 接下來我們再判斷B的兩個子結點D和E,發現這兩個結點得到的結果都是false,于是B是最后一個公共祖先,即是我們的輸出.

這里需要注意的問題是, 如何避免對同一個結點重復遍歷很多次的問題?

比如當我們判斷以結點A為根的樹中是否含有結點F的時候, 我們需要對D,E等結點遍歷一遍；接下來判斷以結點B為根的樹中是否含有結點F時, 我們還是需要對D,E等結點再次遍歷一遍.

解決這個問題的思路是:

在遍歷的過程中使用輔助緩存,用兩個鏈表分別保存從根結點到輸入的兩個結點之間的路徑,然后把問題轉換為兩個鏈表的最后公共結點的問題.

比如我們用前序遍歷的方法得到從根結點A到H的路徑的過程如下:

(1)遍歷到A,將A放入路徑中,路徑中只有一個結點A;

(2)遍歷到B,把B存到路徑中去,此時路徑為A->B;

(3)遍歷到D,把D放到路徑中去,此時路徑為A->B->D;

(4)遍歷到F,把F放到路徑中去,此時路徑為A->B->D->F;

(5)F為葉結點,這條路徑不可能到達節點H,我們需要回溯,把F從路徑中刪除,變為A->B->D;

(6)遍歷到G,和結點F一樣,這條路徑無法到達H,遍歷玩G后,這條路徑仍是A->B->D;

(7)由于D的所有結點都遍歷過了,不可能到達結點H, 因此D不在路徑中,將D從路徑中刪除,變成A->B;

(8)遍歷E,把E加入到路徑中,此時路徑變成A->B->E;

(9)遍歷H,已經到達目標結點,A->B->E就是根結點開始到達H必須經過的路徑.

按照上面的方法,我們同理可以得到從根結點A開始到F必須經過的路徑是A->B->D.

接著,我們求出這兩個路徑的最后公共結點,也就是B,就是我們要求的F和H的最低公共祖先.

時間復雜度分析:

為了得到從根結點開始到輸入的兩個結點的兩條路徑,需要遍歷兩次樹,每次遍歷的時間復雜度是O(n),得到的兩條路徑的長度在最差的情況是O(n),通常情況下兩條路徑的長度是O(logn)

下面是情形三的實現代碼,文件名為common_parent_in_tree.cpp

#include "tree.h"
#include <list>using namespace std;bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path){if(pRoot == pNode)return true;path.push_back(pRoot);bool found = false;vector<TreeNode*>::iterator i = pRoot->vec_children.begin();while(!found && i<pRoot->vec_children.end()){found = GetNodePath(*i, pNode, path);++i;}if(!found)path.pop_back();return found;
}TreeNode* GetLastCommonNode(const list<TreeNode*>& path1, const list<TreeNode*>& path2){list<TreeNode*>::const_iterator iterator1 = path1.begin();list<TreeNode*>::const_iterator iterator2 = path2.begin();TreeNode* pLast = NULL;while(iterator1 != path1.end() && iterator2 != path2.end()){if(*iterator1 == *iterator2)pLast = *iterator1;iterator1++;iterator2++;}return pLast;
}TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2){if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)return NULL;list<TreeNode*> path1;GetNodePath(pRoot, pNode1, path1);list<TreeNode*> path2;GetNodePath(pRoot, pNode2, path2);return GetLastCommonNode(path1,path2);
}//===========================測試代碼==================================void Test(const char* testName, TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2, TreeNode* pExpected){if(testName != NULL)printf("%s begins: \n", testName);TreeNode* pResult = GetLastCommonParent(pRoot, pNode1, pNode2);if((pExpected == NULL && pResult == NULL) ||(pExpected != NULL && pResult != NULL && pResult->value == pExpected->value))printf("Passed.\n");elseprintf("Failed.\n");
}// 形狀普通的樹
//                     1
//                    / \
//                   2   3
//                  / \
//                 4   5
//                /\  /|\
//               6  78 9 10
void Test1(){TreeNode* pNode1 = CreateTreeNode(1);TreeNode* pNode2 = CreateTreeNode(2);TreeNode* pNode3 = CreateTreeNode(3);TreeNode* pNode4 = CreateTreeNode(4);TreeNode* pNode5 = CreateTreeNode(5);TreeNode* pNode6 = CreateTreeNode(6);TreeNode* pNode7 = CreateTreeNode(7);TreeNode* pNode8 = CreateTreeNode(8);TreeNode* pNode9 = CreateTreeNode(9);TreeNode* pNode10 = CreateTreeNode(10);ConnectTreeNodes(pNode1,pNode2);ConnectTreeNodes(pNode1,pNode3);ConnectTreeNodes(pNode2,pNode4);ConnectTreeNodes(pNode2,pNode5);ConnectTreeNodes(pNode4,pNode6);ConnectTreeNodes(pNode4,pNode7);ConnectTreeNodes(pNode5,pNode8);ConnectTreeNodes(pNode5,pNode9);ConnectTreeNodes(pNode5,pNode10);Test("Test1", pNode1, pNode6, pNode8, pNode2);
}//樹退化為一個鏈表
//                    1
//                   /
//                  2
//                 /
//                3
//               /
//              4
//             /
//            5
void Test2(){TreeNode* pNode1 = CreateTreeNode(1);TreeNode* pNode2 = CreateTreeNode(2);TreeNode* pNode3 = CreateTreeNode(3);TreeNode* pNode4 = CreateTreeNode(4);TreeNode* pNode5 = CreateTreeNode(5);ConnectTreeNodes(pNode1,pNode2);ConnectTreeNodes(pNode2,pNode3);ConnectTreeNodes(pNode3,pNode4);ConnectTreeNodes(pNode4,pNode5);Test("Test2",pNode1,pNode5,pNode4,pNode3);
}//樹退化為一個鏈表,一個結點不在樹中
//                    1
//                   /
//                  2
//                 /
//                3
//               /
//              4
//             /
//            5         6
void Test3(){TreeNode* pNode1 = CreateTreeNode(1);TreeNode* pNode2 = CreateTreeNode(2);TreeNode* pNode3 = CreateTreeNode(3);TreeNode* pNode4 = CreateTreeNode(4);TreeNode* pNode5 = CreateTreeNode(5);ConnectTreeNodes(pNode1,pNode2);ConnectTreeNodes(pNode2,pNode3);ConnectTreeNodes(pNode3,pNode4);ConnectTreeNodes(pNode4,pNode5);TreeNode* pNode6 = CreateTreeNode(6);Test("Test3",pNode1,pNode5,pNode6,NULL);
}//輸入NULL
void Test4(){Test("Test4", NULL, NULL, NULL, NULL);
}int main(int argc, char** argv){Test1();Test2();Test3();Test4();return 0;
}

下面是程序運行結果的截圖:

總結

以上是生活随笔為你收集整理的有一个1亿结点的树,已知两个结点, 求它们的最低公共祖先!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。