要求是這樣的：給定兩顆二叉樹A和B，判斷B是否是A的子樹。

在下面這個例子中可以看到B是A的子樹。



想一想該怎樣解決這個問題呢？

如果B是A的一顆子樹，那么B一定和A的一個顆子樹完全一樣，因此我們可以實現(xiàn)一個函數(shù)isSame來判斷兩顆二叉樹是否完全相同，這個函數(shù)非常容易實現(xiàn)：

bool isSame(TreeNode* a, TreeNode* b) {
    if (a == nullptr && b == nullptr) return true;
    else if (a == nullptr || b == nullptr) return false;
    else return a->val == b->val && isSame(a->left, b->left) && isSame(a->right, b->right);
}

只需要三行代碼就能搞定，該函數(shù)非常簡單：

如果二叉樹a和b都為空，那么顯然返回true

否則如果a為空或者b為空，那么這兩棵樹顯然不相同，返回false

如果不滿足條件1和2，那么如果a和b根節(jié)點的值相同并且其左右子樹都一樣，那么二叉樹a和b是相同的二叉樹，返回true

有了isSame函數(shù)剩下的就簡單啦，我們只需要在遍歷二叉樹a時不斷的調(diào)用isSame函數(shù)判斷是否b是a的子樹相同：



同樣的，只需要三行代碼就能搞定：

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (root == nullptr && subRoot == nullptr) return true;
    else if (root == nullptr || subRoot == nullptr) return false;
    else return isSame(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

代碼非常簡單，就是二叉樹的普通遍歷。

有的同學(xué)可能已經(jīng)發(fā)現(xiàn)了，這種算法的實際上不太高效，原因就在于對于二叉樹a上的每個節(jié)點我們都需要調(diào)用一遍isSame函數(shù)，如果二叉樹a的節(jié)點數(shù)為M、二叉樹b的節(jié)點數(shù)為N，那么該算法的時間復(fù)雜度為O(M*N)。

我們一定對二叉樹a中的每個節(jié)點都調(diào)用一遍isSame函數(shù)嗎？

實際上這并不是必須的。

要能想出更高效的算法，你需要理解編碼的概念。

熟悉md5的同學(xué)都知道，我們可以對任何一個文件計算出md5值，md5就是一串?dāng)?shù)字，就好像指紋一樣，只需要兩個文件完全一樣，那么這兩個文件的md5就完全一樣，因此我們可以通過比較md5來確認(rèn)兩個文件是否完全一樣，在linux下用md5sum命令可以計算一個文件的md5值：

$ md5sum a.c
6004b6a21b274b405a2bd1f1c75a93c7  a.c

同樣的，我們也可以對二叉樹計算“md5”值。

怎么計算呢？

實際上非常簡單。

我們只需要在二叉樹的前序遍歷過程中輸出“遍歷軌跡”，那么就能將一顆二叉樹序列化成一個字符串。

如果二叉樹b是a的子樹，那么必然二叉樹b序列化的后的字符串是a序列化后的字符串的子串。

這樣通過編碼，我們將二叉樹子樹的判斷問題轉(zhuǎn)化為了字符串的子串匹配問題，而字符串匹配問題可以通過經(jīng)典的KMP算法解決。



將二叉樹序列化為字符串的函數(shù)也很簡單：

void serialize(TreeNode* root, string& str) {
    if (root == nullptr) {
        str = str + "#";
    } else {
        str = str  + "," + to_string(root->val);


        serialize(root->left, str);
        serialize(root->right, str);
    }
}

可以看到，該代碼實際上還是二叉樹的遍歷。

既然我們可以將二叉樹序列化了字符串，那么接下來就簡單啦：

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    string a, b;
    serialize(root, a);
    serialize(subRoot, b);
    return a.find(b)!=string::npos;
}

將二叉樹序列化為字符串后只需要判斷字符串b是否是字符串a(chǎn)的子串即可。

從這個題目上我們可以看到信息編碼的重要作用，這也是一種非常值得掌握的思想，有時對解決問題有四兩撥千斤的效果。

審核編輯：劉清