首页 > 其他分享 >【剑指Offer刷题系列】序列化与反序列化二叉树

【剑指Offer刷题系列】序列化与反序列化二叉树

时间：2025-01-06 15:30:44浏览次数：3  
标签：null data self tree 二叉树 序列化 root 刷题

目录

问题描述

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

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

示例

示例 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]

提示

  • 树中结点数在范围 [0, 104] 内
  • -1000 <= Node.val <= 1000

原题链接：：https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/description/ 及 https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/ 。

思路解析

本题要求设计一个算法来实现二叉树的序列化与反序列化。序列化将二叉树转换为字符串，反序列化则将字符串重构为原始的二叉树结构。

核心思路：

  1. 选择遍历方式：

    • 前序遍历（先根遍历）：一种常用的方法，通过递归访问节点，先访问根节点，然后左子树，最后右子树。

  2. 处理空节点：

    • 在序列化过程中，用特殊符号（如 # 或 null）表示空节点，以确保反序列化时能够正确还原树结构。

  3. 序列化过程：

    • 使用前序遍历，将节点值按顺序添加到字符串中，节点之间用逗号分隔。
    • 遇到空节点时，添加特殊符号。

  4. 反序列化过程：

    • 将序列化的字符串按逗号分割，转换为一个列表。
    • 通过递归构建二叉树，按照前序遍历的顺序恢复树结构。

具体步骤：

  1. 序列化：

    • 定义一个递归函数 serialize_helper(node, data)：
      • 如果当前节点为空，添加 null 到 data 列表。
      • 否则，添加节点的值，然后递归序列化左子树和右子树。
    • 在主函数 serialize(root) 中，初始化一个空列表 data，调用辅助函数，并将 data 列表用逗号连接成字符串返回。

  2. 反序列化：

    • 定义一个递归函数 deserialize_helper(data_list)：
      • 取出 data_list 的第一个元素。
      • 如果该元素是 null，返回 None。
      • 否则，创建一个新节点，递归构建其左子树和右子树。
    • 在主函数 deserialize(data) 中，将字符串按逗号分割成列表 data_list，调用辅助函数返回根节点。

复杂度分析：

  • 时间复杂度：

    • 序列化和反序列化都需要遍历每个节点一次，因此时间复杂度为 O(n)，其中 n 是二叉树的节点数。

  • 空间复杂度：

    • 序列化过程中需要存储所有节点的值，空间复杂度为 O(n)。
    • 反序列化过程中递归调用栈的深度与树的高度相关，最坏情况下为 O(n)。

代码实现

Python 实现

# Definition for a binary tree node.
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left: Optional['TreeNode']=None, right: Optional['TreeNode']=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string."""
        data = []
        
        def serialize_helper(node):
            if node is None:
                data.append('null')
                return
            data.append(str(node.val))
            serialize_helper(node.left)
            serialize_helper(node.right)
        
        serialize_helper(root)
        return ','.join(data)
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""
        data_list = data.split(',')
        self.index = 0
        
        def deserialize_helper():
            if self.index >= len(data_list):
                return None
            val = data_list[self.index]
            self.index += 1
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = deserialize_helper()
            node.right = deserialize_helper()
            return node
        
        return deserialize_helper()

测试代码

import unittest

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string."""
        data = []
        
        def serialize_helper(node):
            if node is None:
                data.append('null')
                return
            data.append(str(node.val))
            serialize_helper(node.left)
            serialize_helper(node.right)
        
        serialize_helper(root)
        return ','.join(data)
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""
        data_list = data.split(',')
        self.index = 0
        
        def deserialize_helper():
            if self.index >= len(data_list):
                return None
            val = data_list[self.index]
            self.index += 1
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = deserialize_helper()
            node.right = deserialize_helper()
            return node
        
        return deserialize_helper()

class TestCodec(unittest.TestCase):
    def build_tree_from_list(self, lst):
        """Helper function to build tree from level-order list."""
        if not lst:
            return None
        root = TreeNode(lst[0])
        queue = deque([root])
        i = 1
        while queue and i < len(lst):
            current = queue.popleft()
            if current:
                # Assign left child
                if i < len(lst) and lst[i] is not None:
                    current.left = TreeNode(lst[i])
                queue.append(current.left)
                i += 1
                # Assign right child
                if i < len(lst) and lst[i] is not None:
                    current.right = TreeNode(lst[i])
                queue.append(current.right)
                i += 1
        return root

    def trees_are_equal(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        """Helper function to compare two trees."""
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val and 
                self.trees_are_equal(t1.left, t2.left) and 
                self.trees_are_equal(t1.right, t2.right))
    
    def test_example1(self):
        codec = Codec()
        tree = [1,2,3,None,None,4,5]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "1,2,null,null,3,4,null,null,5,null,null"
        self.assertEqual(serialized, expected, "示例1序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "示例1反序列化失败")
    
    def test_example2(self):
        codec = Codec()
        tree = []
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "null"
        self.assertEqual(serialized, expected, "示例2序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "示例2反序列化失败")
    
    def test_example3(self):
        codec = Codec()
        tree = [1]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "1,null,null"
        self.assertEqual(serialized, expected, "示例3序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "示例3反序列化失败")
    
    def test_example4(self):
        codec = Codec()
        tree = [1,2]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "1,2,null,null,null"
        self.assertEqual(serialized, expected, "示例4序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "示例4反序列化失败")
    
    def test_single_node(self):
        codec = Codec()
        tree = [10]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "10,null,null"
        self.assertEqual(serialized, expected, "单节点序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "单节点反序列化失败")
    
    def test_left_skewed(self):
        codec = Codec()
        tree = [1,2,None,3,None,4,None]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "1,2,3,4,null,null,null,null,null"
        self.assertEqual(serialized, expected, "左倾序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "左倾反序列化失败")
    
    def test_right_skewed(self):
        codec = Codec()
        tree = [1,None,2,None,3,None,4]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "1,null,2,null,3,null,4,null,null"
        self.assertEqual(serialized, expected, "右倾序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "右倾反序列化失败")
    
    def test_complex_tree(self):
        codec = Codec()
        tree = [5,3,8,1,4,7,9,None,2]
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "5,3,1,null,2,null,null,4,null,null,8,7,null,null,9,null,null"
        self.assertEqual(serialized, expected, "复杂树序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "复杂树反序列化失败")
    
    def test_null_tree(self):
        codec = Codec()
        tree = []
        root = self.build_tree_from_list(tree)
        serialized = codec.serialize(root)
        expected = "null"
        self.assertEqual(serialized, expected, "空树序列化失败")
        deserialized = codec.deserialize(serialized)
        self.assertTrue(self.trees_are_equal(root, deserialized), "空树反序列化失败")

if __name__ == "__main__":
    from collections import deque
    unittest.main(argv=[''], exit=False)

输出：

.........
----------------------------------------------------------------------
Ran 8 tests in 0.XXXs

OK

复杂度分析

时间复杂度

  • 序列化：

    • 需要遍历每个节点一次，时间复杂度为 O(n)，其中 n 是二叉树的节点数。

  • 反序列化：

    • 需要遍历序列化后的字符串中的每个元素一次，时间复杂度为 O(n)，其中 n 是二叉树的节点数。

空间复杂度

  • 序列化：

    • 需要存储序列化结果，空间复杂度为 O(n)。

  • 反序列化：

    • 需要存储所有节点值的列表，空间复杂度为 O(n)。
    • 递归调用栈的空间复杂度与树的高度相关，最坏情况下为 O(n)。

通过上述方法，我们可以高效地实现二叉树的序列化与反序列化。采用前序遍历的方法简单直观，确保了序列化后的字符串能够完整地表示二叉树的结构。在实际应用中，这种方法适用于需要存储或传输二叉树结构的场景。

标签：null,data,self,tree,二叉树,序列化,root,刷题
From： https://blog.csdn.net/weixin_44329069/article/details/144959109

相关文章

  • 【剑指Offer刷题系列】数组中数字出现的次数 II
    目录问题描述示例示例1：示例2：思路解析核心思路：具体步骤：复杂度分析：代码实现Python实现测试代码复杂度分析时间复杂度空间复杂度结论问题描述教学过程中，教练示范一次，学员跟做三次。该过程被混乱剪辑后，记录于数组actions，其中actions[i]表示做出该动作的人员......
  • 【剑指Offer刷题系列】整数拆分 II
    目录问题描述示例示例1：示例2：示例3：思路解析核心思路：具体步骤：复杂度分析：代码实现Python实现测试代码复杂度分析时间复杂度空间复杂度结论问题描述现需要将一根长度为正整数bamboo_len的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积......
  • 【剑指Offer刷题系列】数值的整数次方
    目录问题描述示例示例1：示例2：示例3：思路解析核心思路：具体步骤：复杂度分析：代码实现Python实现测试代码复杂度分析时间复杂度空间复杂度结论问题描述实现pow(x,n)，即计算x的n次幂函数（即，x^n）。注意：x是一个双精度浮点数。n是一个整数，可以是正数、负数或零......
  • AtCoder备赛刷题 ABC 361 | x = a^b
    学习C++从娃娃抓起！记录下AtCoder（日本算法竞技网站）备赛学习过程中的题目，记录每一个瞬间。附上汇总贴：AtCoder备赛刷题|汇总【ProblemStatement】Howmanyintegersxx......
  • AtCoder备赛刷题 ABC 361 | Go Territory
    学习C++从娃娃抓起！记录下AtCoder（日本算法竞技网站）备赛学习过程中的题目，记录每一个瞬间。附上汇总贴：AtCoder备赛刷题|汇总【ProblemStatement】ThereareNNNston......
  • 重生之我在异世界学编程之数据结构与算法：深入数和二叉树篇
    大家好，这里是小编的博客频道小编的博客：就爱学编程很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！目录一、树的基本概念二、二叉树的基本概念三、在C语言中实现二叉树快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞......
  • 二叉树
    描述小杨有⼀棵包含 n 个节点的二叉树，且根节点的编号为 1。这棵二叉树任意⼀个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 q 次操作，每次小杨会选择⼀个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。小杨想知道 q 次操作全......
  • LeetCode算法题 （二叉树的直径）Day11！！！C/C++
    https://leetcode.cn/problems/diameter-of-binary-tree/description/一、题目描述给你一棵二叉树的根节点，返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它......
  • 124.二叉树中的最大路径和
    /***@param{TreeNode}root*@return{number}*///子树的最大路径和=左子树提供的最大路径和+根节点值+右子树的的最大路径和，//分别递归遍历左子树和右子树的最大路径和，两者之前取一个最大值；返回；//最后里面，要注意最后得出的是一个负数，直接返回0；否则正常的数据......
  • 编程题-二叉树的中序遍历
    题目：给定一个二叉树的根节点root，返回它的中序 遍历。解答一（递归）：首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99