• 剑指 Offer II 048. 序列化与反序列化二叉树


    题目链接

    力扣

    题目描述

    序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

    请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

    示例 1:

    输入:root = [1,2,3,null,null,4,5]
    输出:[1,2,3,null,null,4,5]
    示例 2:

    输入:root = []
    输出:[]
    示例 3:

    输入:root = [1]
    输出:[1]
    示例 4:

    输入:root = [1,2]
    输出:[1,2]
     

    提示:

    输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,也可以采用其他的方法解决这个问题。
    树中结点数在范围 [0, 104] 内
    -1000 <= Node.val <= 1000

    解题思路

    dfs,先序遍历,难点在于反序列化,当时没绕过弯来。

    Go这里用到了strings.Builder,这个常用于拼接字符串

    代码

    Python

    1. class Codec:
    2. def serialize(self, root: TreeNode) -> str:
    3. """Encodes a tree to a single string.
    4. :type root: TreeNode
    5. :rtype: str
    6. """
    7. if not root:
    8. return 'None'
    9. root.left = self.serialize(root.left)
    10. root.right = self.serialize(root.right)
    11. return f"{root.val},{root.left},{root.right}"
    12. def deserialize(self, data: str) -> TreeNode:
    13. """Decodes your encoded data to tree.
    14. :type data: str
    15. :rtype: TreeNode
    16. """
    17. queue = data.split(',')
    18. def build(queue):
    19. val = queue.pop(0)
    20. if val == 'None':
    21. return None
    22. root = TreeNode(int(val))
    23. root.left = build(queue)
    24. root.right = build(queue)
    25. return root
    26. return build(queue)

    Go

    1. type Codec struct {
    2. }
    3. func Constructor() Codec {
    4. return Codec{}
    5. }
    6. // Serializes a tree to a single string.
    7. func (this *Codec) serialize(root *TreeNode) string {
    8. var sb strings.Builder
    9. var dfs func(*TreeNode)
    10. dfs = func(node *TreeNode) {
    11. if node == nil {
    12. sb.WriteString("null,")
    13. return
    14. }
    15. sb.WriteString(strconv.Itoa(node.Val))
    16. sb.WriteByte(',')
    17. dfs(node.Left)
    18. dfs(node.Right)
    19. }
    20. dfs(root)
    21. return sb.String()
    22. }
    23. // Deserializes your encoded data to tree.
    24. func (this *Codec) deserialize(data string) *TreeNode {
    25. queue := strings.Split(data, ",")
    26. var build func() *TreeNode
    27. build = func() *TreeNode {
    28. if queue[0] == "null" {
    29. queue = queue[1:]
    30. return nil
    31. }
    32. val, _ := strconv.Atoi(queue[0])
    33. queue = queue[1:]
    34. return &TreeNode{
    35. Val: val,
    36. Left: build(),
    37. Right: build(),
    38. }
    39. }
    40. return build()
    41. }

  • 相关阅读:
    网络服务---OSI七层参考模型及各层工作原理详解
    Vue/JS自定义指令:实现元素滑动、移动端适配以及边界处理
    leetcode 649. Dota2 参议院
    WebServer——二:线程池
    Docker部署可能遇到的问题
    小程序中如何核销订单和优惠券
    Netty启动之后马上退出问题排查
    Axure RP仿QQ音乐app高保真原型图交互模板源文件
    ESP8266--SDK开发(延时、定时器)
    C++模板初阶
  • 原文地址:https://blog.csdn.net/qq_33523932/article/details/125558676