【Day 17 】2024-08-31 - 297. 二叉树的序列化与反序列化

[azl397985856]

297. 二叉树的序列化与反序列化

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

前置知识

暂无

题目描述

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

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

示例: 

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

[akxuan]

可以用 dfs 和bfs 写。 效果都差不多。 dfs 的话就是前序遍历， 先处理 node， 然后再处理左右。 bfs 的话就可以用层序遍历或者bfs 模版。 注意第一个deseries 返回的是一个string

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        # bfs
        res = ''
        q = collections.deque([root])
        while q : 
            tmp = q.popleft()
            if not tmp: 
                res += 'n,'
            else: 
                res += str(tmp.val)
                res += ','
                q.append(tmp.left)
                q.append(tmp.right)

        return res

        ''' # dfs
        self.res = ''
        def helper(root):
            if not root:
                self.res += 'n,'
            else:
                self.res += str(root.val) + ','
                helper(root.left)
                helper(root.right)

        helper(root)
        print(self.res)
        return self.res
        '''

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        ''' #dfs
        def helper(l):
            if l[0] == 'n':
                l.popleft()
                return None 
            root = TreeNode(l.popleft())
            root.left = helper(l)
            root.right = helper(l)
            return root

        data_list = data.split(',')
        data_list = collections.deque(data_list)

        root = helper(data_list)
        return root
        '''

        # bfs
        data_list = data.split(',')
        data_list = collections.deque(data_list)

        if not data_list or data_list[0] == 'n':
            return None

        root = TreeNode(data_list.popleft())
        q = collections.deque([root])

        while q:
            curr = q.popleft()

            if data_list:
                left_val = data_list.popleft()
                if left_val != 'n':
                    curr.left = TreeNode(left_val)
                    q.append(curr.left)

            if data_list:
                right_val = data_list.popleft()
                if right_val != 'n':
                    curr.right = TreeNode(right_val)
                    q.append(curr.right)

        return root

时间复杂度和空间复杂度都是 o（N） N 为number of node

[edwineo]

思路

dfs 前序遍历

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    if (!root) {
        return 'X' // 空的用 X 表示
    }
    const left = serialize(root.left)
    const right = serialize(root.right)
    return `${root.val},${left},${right}`
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const list = data.split(',') // data 本身是字符串
    const buildTree = (list) => {
        const rootVal = list.shift() // 一定要先取出来 root 值
        if (rootVal === 'X') { // 空的用 X 表示
            return null
        }
        // 如果 rootVal 有值
        const root = new TreeNode(rootVal)
        root.left = buildTree(list) // 下一个就是 left，递归构建 left 子树
        root.right = buildTree(list) // 再下一个是 right，递归构建 right 子树
        return root // 返回构建的根节点
    }
    return buildTree(list)
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

复杂度

时间复杂度：O(N) ，N 为 number of node 空间复杂度：O(N)

[huizsh]

class Codec:

# BFS 遍历二叉树
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        queue = deque([root])
        result = ''
        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                item = queue.popleft()
                if not item:
                    result += "null,"
                else:
                    result += str(item.val) + ","
                    queue.append(item.left)
                    queue.append(item.right)
        return result[:-1]

#https://leetcode-solution.cn/solutionDetail?type=3&id=17&max_id=2
#用三个指针分别指向数组第一项，第二项和第三项（如果存在的话），这里用 p1，p2，p3 来标记，分别表示当前处理的节点，当前处理的节点的左子节点和当前处理的节点的右子节点。
#p1 每次移动一位，p2 和 p3 每次移动两位。
#p1.left = p2; p1.right = p3。
#持续上面的步骤直到 p1 移动到最后。

    def deserialize(self, data):
        if data == 'null': return None
        nodes = data.split(',')
        root = TreeNode(nodes[0])
        q = collections.deque([root])
        i = 0
        while q and i < len(nodes) - 2:
            cur = q.popleft()
            lv = nodes[i + 1]
            rv = nodes[i + 2]
            i = i + 2
            if lv != "null":
                l = TreeNode(lv)
                q.append(l)
                cur.left = l
            if rv != "null":
                r = TreeNode(rv)
                q.append(r)
                cur.right = r
        return root

[peggyhao]

public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
    }
}

[zjy-debug]

代码

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """

        def dfs(node):
            if not node:
                return "null,"
            return str(node.val) + "," + dfs(node.left) + dfs(node.right)

        return dfs(root)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        def dfs(nodes):
            val = next(nodes)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = dfs(nodes)
            node.right = dfs(nodes)
            return node

        node_values = iter(data.split(","))
        return dfs(node_values)

[Forschers]

public class Codec { public String serialize(TreeNode root) { if(root==null) return "null"; return root.val+","+serialize(root.left)+","+serialize(root.right); } public TreeNode deserialize(String data) { String[] req=data.split(","); ArrayList r=new ArrayList<>(Arrays.asList(req)); return dfsdeserialize(r);
}

public TreeNode dfsdeserialize(ArrayList<String> r){
    if("null".equals(r.get(0))){
        r.remove(0);
        return null;
    }
    TreeNode node=new TreeNode(Integer.valueOf(r.get(0)));
    r.remove(0);
    node.left=dfsdeserialize(r);
    node.right=dfsdeserialize(r);
    return node;
}

}

[Fightforcoding]

Algorithm

DFS

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

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        def helper (node):
            if not node:
                val.append('#')
                return
            val.append(str(node.val))
            helper(node.left)
            helper(node.right)
        val = []
        helper(root)
        return ','.join(val)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        def helper():
            if not val:
                return None
            v = val.popleft()
            if v == '#':
                return None
            node = TreeNode(int(v))
            node.left = helper()
            node.right = helper()
            return node
        val = collections.deque(data.split(','))
        return helper()

Time: O(n) Space: O(n)