好久没发算法的文章了，今天我们来看一个有趣的算法题，也是一道高频面试题。这个题目是leetcode的第572题，要求是这样的：给定两颗二叉树A和B，判断B是否是A的子树。如果B是A的一颗子树，那么B一定和A的一个颗子树完全一样，因此我们可以实现一个函数isSame来判断两颗二叉树是否完全相同，这个函数非常容易实现：
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);}
- 否则如果a为空或者b为空，那么这两棵树显然不相同，返回false
- 如果不满足条件1和2，那么如果a和b根节点的值相同并且其左右子树都一样，那么二叉树a和b是相同的二叉树，返回true
有了isSame函数剩下的就简单啦，我们只需要在遍历二叉树a时不断的调用isSame函数判断是否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);}
有的同学可能已经发现了，这种算法的实际上不太高效，原因就在于对于二叉树a上的每个节点我们都需要调用一遍isSame函数，如果二叉树a的节点数为M、二叉树b的节点数为N，那么该算法的时间复杂度为O(M*N)。我们一定对二叉树a中的每个节点都调用一遍isSame函数吗？实际上这并不是必须的。熟悉md5的同学都知道，我们可以对任何一个文件计算出md5值，md5就是一串数字，就好像指纹一样，只需要两个文件完全一样，那么这两个文件的md5就完全一样，因此我们可以通过比较md5来确认两个文件是否完全一样，在linux下用md5sum命令可以计算一个文件的md5值：
$ md5sum a.c6004b6a21b274b405a2bd1f1c75a93c7 a.c
我们只需要在二叉树的前序遍历过程中输出“遍历轨迹”，那么就能将一颗二叉树序列化成一个字符串。如果二叉树b是a的子树，那么必然二叉树b序列化的后的字符串是a序列化后的字符串的子串。这样通过编码，我们将二叉树子树的判断问题转化为了字符串的子串匹配问题，而字符串匹配问题可以通过经典的KMP算法解决。
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的子串即可。从这个题目上我们可以看到信息编码的重要作用，这也是一种非常值得掌握的思想，有时对解决问题有四两拨千斤的效果。
