面试官：这么简单的二叉树算法都不会？

2023-05-23 00:00:00 函数子树二叉树字符串遍历

好久没发算法的文章了，今天我们来看一个有趣的算法题，也是一道高频面试题。

这个题目是leetcode的第572题，要求是这样的：给定两颗二叉树A和B，判断B是否是A的子树。

在下面这个例子中可以看到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都为空，那么显然返回true
否则如果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

同样的，我们也可以对二叉树计算“md5”值。

怎么计算呢？实际上非常简单。

我们只需要在二叉树的前序遍历过程中输出“遍历轨迹”，那么就能将一颗二叉树序列化成一个字符串。

如果二叉树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的子串即可。

从这个题目上我们可以看到信息编码的重要作用，这也是一种非常值得掌握的思想，有时对解决问题有四两拨千斤的效果。

相关文章