python二叉树的序列化该怎么理解
本篇文章给大家分享的是有关python二叉树的序列化该怎么理解，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。
设计一个算法，序列化和反序列化一棵二叉树。
解释：序列化的意思是将内存中的一些特定的结构，变成有格式信息的字符串。
如，对于链表而言，我们可以将1->2->3->NULL这样的链表序列化为"1,2,3"。对于序列化算法，必须支持反序列化，及在约定的格式下，可以将满足格式要求的字符串重新构造为想要的结构。
答：
使用BFS。对于下面这棵二叉树：
1
/ \
2 3
/ \
4 5
BFS序为：[1,2,3,4,5]。如果我们将叶子节点的左右儿子用#来表示的话，可以得到下面这棵树：
1
/ \
2 3
/ \ / \
# # 4 5
/ \ / \
# # # #
一行一行看可以得到：[1,2,3,#,#,4,5,#,#,#,#]
去掉尾部连续的#，可以得到[1,2,3,#,#,4,5]，这样就完成了使用BFS来序列化。
同样的，我们也可以使用DFS进行序列化，DFS序列化的结果如下：[1,2,#,#,3,4,#,#,5,#,#]，去掉末尾的#得到[1,2,#,#,3,4,#,#,5]，要比BFS序列化的结果要长。原因主要在于大部分的#出现在最底层，所以BFS的方式可以使得尽量多的#都在序列化的尾部。
面试官角度：
所谓的序列化，是将一个结构化的东西变成扁平化的字符串。这样可以方便传输和进行压缩等。使用BFS或者DFS的方法在面试中都是正确的，但如果能够比较出BFS的方法可以更有效的节省空间的话，可以得到额外的加分。
以上就是python二叉树的序列化该怎么理解，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注蜗牛博客行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
评论