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

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



想一想該怎樣解決這個(gè)問(wèn)題呢？

如果B是A的一顆子樹，那么B一定和A的一個(gè)顆子樹完全一樣，因此我們可以實(shí)現(xiàn)一個(gè)函數(shù)isSame來(lái)判斷兩顆二叉樹是否完全相同，這個(gè)函數(shù)非常容易實(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ù)非常簡(jiǎn)單：

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

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

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

有了isSame函數(shù)剩下的就簡(jiǎn)單啦，我們只需要在遍歷二叉樹a時(shí)不斷的調(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);
}

代碼非常簡(jiǎn)單，就是二叉樹的普通遍歷。

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

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

實(shí)際上這并不是必須的。

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

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

$ md5sum a.c
6004b6a21b274b405a2bd1f1c75a93c7  a.c

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

怎么計(jì)算呢？

實(shí)際上非常簡(jiǎn)單。

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

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

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



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

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);
    }
}

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

既然我們可以將二叉樹序列化了字符串，那么接下來(lái)就簡(jiǎn)單啦：

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)的子串即可。

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

審核編輯：劉清