查看原文
其他

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

脚本之家 2023-09-03

The following article is from 码农的荒岛求生 Author 码农的荒岛求生

将 脚本之家 设为“星标
第一时间收到文章更新

出品 | 码农的荒岛求生 (ID:escape-it)

已获得原公众号的授权转载

好久没发算法的文章了,今天我们来看一个有趣的算法题,也是一道高频面试题。
这个题目是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);}
只需要三行代码就能搞定,该函数非常简单:
  1. 如果二叉树a和b都为空,那么显然返回true
  2. 否则如果a为空或者b为空,那么这两棵树显然不相同,返回false
  3. 如果不满足条件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的子串即可。
从这个题目上我们可以看到信息编码的重要作用,这也是一种非常值得掌握的思想,有时对解决问题有四两拨千斤的效果
<END>

程序员专属T恤

商品直购链接 👇


  推荐阅读:
据说,这是一件程序员才懂的T恤
刚刚!Twitter算法开源,Star数已1.5w+
为什么你学算法容易忘?
面试必会的算法题——求加法
注意:雪花算法并不是ID的唯一选择!
Office 2019/2021专业增强版,正版终身授权!

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存