Leetcode刷题java之297. 二叉树的序列化与反序列化

桃扇骨 2023-07-04 12:51 17阅读 0赞

执行结果：

通过

显示详情

执行用时 :108 ms, 在所有 Java 提交中击败了21.70% 的用户

内存消耗 :51.6 MB, 在所有 Java 提交中击败了5.10%的用户

题目：

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

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

示例:

你可以将以下二叉树：

1  
/ \\  
2 3  
/ \\  
4 5

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

关键点一，采用前序遍历进行序列化和反序列化

关键点二，格式值+空格+值，空节点用\#代替

代码：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        // Encodes a tree to a single string.
        String remainString;
        public String serialize(TreeNode root) {
            if(root==null)
            {
                return "#";
            }
            return root.val+" "+serialize(root.left)+" "+serialize(root.right);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            remainString=data;
            return deserialize();
        }
        public TreeNode deserialize()
        {
            if(remainString==null)
            {
                return null;
            }
            int index=remainString.indexOf(" ");
            String node=index==-1?remainString:remainString.substring(0,index);
            remainString=index==-1?"":remainString.substring(index+1);
            if(node.equals("#"))
            {
                return null;
            }
            int val=Integer.parseInt(node);
            TreeNode root=new TreeNode(val);
            root.left=deserialize();
            root.right=deserialize();
            return root;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));