869
海量數據：判斷一棵樹是否為另一棵樹的子樹
T1是一棵含有幾百萬個節點的樹，T2含有幾百個節點。判斷T2是否是T1 的子樹。
首先考慮小數據量的情況，可以根據樹的前序和中序遍曆所得的字符串，來通過判斷T2生成的字符串是否是T1字符串的子串，來判斷T2是否是T1的子樹。假設T1的節點數為N，T2的節點數為M。遍曆兩棵樹算法時間複雜性是O(N + M)， 判斷字符串是否為另一個字符串的子串的複雜性也是O( N + M)（比如使用KMP算法）。所需要的空間也是O(N + M)。
這裏有一個問題需要注意：對於左節點或者右節點為null的情況，需要在字符串中插入特殊字符表示。否則對於下麵這種情形將會判斷錯誤：
因此如果插入特殊字符，上述兩棵樹的中序和前序遍曆的結果是相同的。
由於本例有幾百萬的節點，需要占用O(N + M)的內存。
如果換一種思路，就是遍曆T1，每當T1的某個節點與T2的根節點值相同時，就判斷兩棵子樹是否相同。這個算法的複雜度是O(N*M)。我們再仔細思考一下。因為隻有在節點值與T2的根節點值相同才會調用O(M)。假設有K次這種情況，那麼算法的複雜度就是O(N + K*M)。下麵是代碼實現：
struct TreeNode{
TreeNode *leftChild;
TreeNode *rightChild;
int data;
};
// check sub tree n1 == sub tree n2
bool checkSubTree(const TreeNode* n1, const TreeNode* n2){
if( n1 == nullptr && n2 == nullptr )
return true;
if( n1 == nullptr || n2 == nullptr )
return false;
if( n1->data != n2->data )
return false;
return checkSubTree(n1->leftChild, n2->leftChild) && checkSubTree(n1->rightChild, n2->rightChild);
}
bool subTree(const TreeNode *n1, const TreeNode *n2){
if( n1 == nullptr){
return false; // the bigger tree is empty, so t2 is not subtree of t1
}
if( n1->data == n2->data){
if( checkSubTree(n1, n2))
return true;
}
return subTree(n1->leftChild, n2) || subTree(n2->rightChild, n2);
}
對於上麵討論的2種解法，哪種解法比較好呢？其實有必要好好討論一番：
1）方法一會占用O(N + M)的內存，而另外一種解法隻會占用O(logN + logM)的內存（遞歸的棧內存）。當考慮scalability擴展性時，內存使用的多寡是個很重要的因素。
2）方法一的時間複雜度為O(N + M)，方法二最差的時間複雜度是O(N*M)。所以要通過工程實踐或者是曆史數據看一下哪種方法更優。當然了，方法二也可能會很早發現兩棵樹的不同，早早的退出了checkSubTree。
總的來說，在空間使用上，方法二更好。在時間上，需要通過實際數據來驗證。
最後更新：2017-04-03 12:54:00