当前位置:首页 > 服务端 > LeetCode | 面试题37. 序列化二叉树【剑指 Offer】【Python】

LeetCode | 面试题37. 序列化二叉树【剑指 Offer】【Python】

2022年08月06日 10:28:01服务端4

问题

力扣

请实现两个函数,分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树:
	1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

注意:本题与主站 297 题相同:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

思路

BFS

代码

Python3

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        import collections
        if not root:
            return "[]"
        
        queue = collections.deque()
        queue.append(root)
        res = []
        # 层序遍历BFS
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append("null")
        return "[" + ",".join(res) + "]"
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        import collections
        if data == "[]":
            return
        
        # 去掉首尾括号,根据逗号进行切片
        vals, i = data[1:-1].split(","), 1
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            # 构建左子树
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            # 构建右子树
            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

链接

GitHub

面试题37. 序列化二叉树(层序遍历 BFS ,清晰图解)

作者:Wonz
来源链接:https://www.cnblogs.com/wonz/p/14466278.html

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/server/18241.html

分享给朋友:

“LeetCode | 面试题37. 序列化二叉树【剑指 Offer】【Python】” 的相关文章

Spring Cloud面试问题

Spring Cloud面试问题

问:什么是Spring Cloud?     答: Spring Cloud Stream App Starters是基于Spring Boot的Spring Integration应用程序,提供与外部系统的集成。Spring Cloud Task。...

MySQL面试有这一篇就够了

MySQL面试有这一篇就够了

MySQL面试常见知识点 1、 MySQL常用的存储引擎有什么?它们有什么区别? InnoDB InnoDB是MySQL的默认存储引擎,支持事务、行锁和外键等操作。 MyISAM MyISAM是M...

什么是软件实施?软件实施前景几何?软件实施的面试题有那些?

事情是这样的,由于自己目前还没有对象,就想着在兰州找一份还不错的工作,于是投了一家在我的家乡还算不错的公司,对方却说有可能是软件实施岗位,于是趁机了解了一下, 什么是软件实施? 软件实施掌握的基础知识有哪些? 软件实施前景几何?...

IOS面试题详解(二)..

IOS面试题详解(二)..

上一篇文章列出了共32道IOS面试题: http://www.cnblogs.com/fkdd/archive/2012/03/13/2394724.html 下面从第一题开始解答: 题目:1.Object-c的类可以多重继承么?可以实现多个接口么?Category是什么?...

一文高效图解二叉树面试题

一文高效图解二叉树面试题

点击蓝色“码出高效面试的程序媛”关注我, 了解更多技术流行面试题 二叉树,搜索二叉树,是算法面试的必面题。聊聊面试点: 一、树 & 二叉树 树的组成为节点和边,节点用来储存元素。节点组成为根节点、父节点和子节点。 如图:树深 leng...

Java面试题:Error和Exception有什么区别?

[ Error表示系统级的错误和程序不必处理的异常,是恢复不是不可能但很困难的情况下的一种严重问题;比如内存溢出,不可能指望程序能处理这样的情况;Exception表示需要捕捉或者需要程序进行处理的异常,是一种设计或实现问题;也就是说,它表示如果程序运行正常,从不会发生的...

59面试常问:MySQL索引是如何提高查询效率的呢?(MySQL面试第二弹)

59面试常问:MySQL索引是如何提高查询效率的呢?(MySQL面试第二弹)

  About MySQL MySQL(读作/maɪ ˈsiːkwəl/“My Sequel”)是一个开放源码的关系数据库管理系统,原开发者为瑞典的MySQL AB公司,目前为Oracle旗下产品。 被甲骨文公司收购后,自由软件社群们...

也说面试 - 一个努力的iOS Dev

  你们在金色的余晖中回家,而我却在银色的温柔中,匆匆潜行-----这是我的现状。   今年的招工形式不是很好,难找工作;也难招人。写这篇博客,是为了给各位在找工作的iOS dev 一些参考。 上篇:换坑(去面试)   又是一年换坑的时节,出于各种原因,我又换坑了。...

java基础面试题:运行时异常与一般异常有何异同?error和exception有什么区别? 请写出你最常见到的5个runtimeexception?

Throwable是Java错误处理的父类,有两个子类:Error和Exception。   Error:无法预期的严重错误,导致JVM虚拟机无法继续执行,几乎无法恢复捕捉的 Exception:可恢复捕捉的。java健壮程序的手段。  ...

rabbitmq面试题

rabbit面试题 1.什么是rabbitmq 采用AMQP高级消息队列协议的一种消息队列技术,最大的特点就是消费并不需要确保提供方存在,实现了服务之间的高度解耦 2.为什么要使用rabbitmq 1.在分布式系统下具备异步,削峰...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。