今天我們來(lái)看一個(gè)有趣的算法題，也是一道高頻面試題。

這個(gè)題目是leetcode的第572題，要求是這樣的：給定兩顆二叉樹(shù)A和B，判斷B是否是A的子樹(shù)。

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

想一想該怎樣解決這個(gè)問(wèn)題呢？如果B是A的一顆子樹(shù)，那么B一定和A的一個(gè)顆子樹(shù)完全一樣，因此我們可以實(shí)現(xiàn)一個(gè)函數(shù)isSame來(lái)判斷兩顆二叉樹(shù)是否完全相同，這個(gè)函數(shù)非常容易實(shí)現(xiàn)：

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

1. 如果二叉樹(shù)a和b都為空，那么顯然返回true

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

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

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

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

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

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

我們一定對(duì)二叉樹(shù)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值：

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)??

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

怎么計(jì)算呢？實(shí)際上非常簡(jiǎn)單。

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

如果二叉樹(shù)b是a的子樹(shù)，那么必然二叉樹(shù)b序列化的后的字符串是a序列化后的字符串的子串。這樣通過(guò)編碼，我們將二叉樹(shù)子樹(shù)的判斷問(wèn)題轉(zhuǎn)化為了字符串的子串匹配問(wèn)題，而字符串匹配問(wèn)題可以通過(guò)經(jīng)典的KMP算法解決。

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

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

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

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

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

原文作者：碼農(nóng)的荒島求生