1532 · 序列化和反序列N叉树

Difficulty

Hard

Tags

二叉树

URL

https://www.lintcode.com/problem/1532/

Star

描述

序列化是将一个数据结构或对象转换成比特流的过程，以便将其存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一或另一计算机环境中重建。

设计一个算法来序列化和反序列化一个N叉树。一棵N叉树是一棵有根树，其中每个节点的子节点不超过N个。序列化/反序列化算法的实现方式没有限制。您只需要确保N叉树可以序列化为字符串，并且该字符串可以反序列化为原始树结构。

例如，你可以序列化如下的3叉树

为 [1 [3[5 6] 2 4]]。你不一定要遵循这种格式，发挥创意，自己想出不同的方法。

Example 1:


Input：{1,3,2,4#2#3,5,6#4#5#6}
Output：{1,3,2,4#2#3,5,6#4#5#6}
Explanation：Pictured above

Example 2:


Input：{1,3,2#2#3}
Output：{1,3,2#2#3}
Explanation：
    1
	 / \
	3   2

法1 先序遍历

思路

每个节点的子节点数量未知，所以把子节点数量也编码进去。

序列化的字符串为，节点值，子节点个数。例如N叉树

序列化的结果为 [1, 3, 3, 2, 5, 0, 6, 0, 2, 0, 4, 0]

反序列化的时候类似二叉树，只不过是N叉树，所以要弹出N次，又因为是先序遍历，所以递归的实现

题解


"""
Definition for a directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""


class Solution:
    def serialize(self, root):
        res = []
        self.dfs_s(root, res)
        return ",".join(res)
    # 辅助序列化
    def dfs_s(self,root, res):
        if root is None:
            return
        
        res.append(str(root.label))
        res.append(len(root.neighbors))
        for child in root.neighbors:
            self.dfs_s(child, res)
        
    def deserialize(self, data):
        if len(data) == 0:
            return None
        data = data.split(",")
        return self.dfs_d(data)
    
    # 辅助反序列化
    def dfs_d(self,data):
        if len(data) == 0:
            return
				# 第一次 弹出节点值
        cur_node = DirectedGraphNode(int(data.pop(0)), [])
				# 第二次 弹出子节点个数   
        size = data.pop()
        for _ in range(size):
            cur_node.neighbors.append(self.dfs_d(data))

        return cur_node

1532 · 序列化和反序列N叉树 - LintCode

法1 先序遍历