LeetCode-297.Serialize and Deserialize Binary Tree(二叉树的序列化和反序列化)

LeetCode-297.Serialize and Deserialize Binary Tree(二叉树的序列化和反序列化)

• 题意及解题思路
• 层序序列化和层序反序列化
• 完整测试代码

---

题目链接

题意

当然上面这个是按层序列化，我们也可以按前序序列化，只要能通过序列化的结果还原二叉树即可。

解析

前序序列化，就是将当前的树按照前序的方式生成一个字符串，如果结点不为空，就是结点的value，如果结点为null，就用”null“来代替。

逻辑很简单，直接上前序序列化代码
由于说最好不要使用全局变量，所以这里反序列化的时候使用了一个idx数组(大小为1)。

public class Codec {
    
    public String serialize(TreeNode root){
        StringBuilder res = new StringBuilder();
        serialByPre(root,res);
        res.deleteCharAt(res.length()-1);//将最后一个,删除
        return res.toString();
    }

    //前序序列化二叉树
    public void serialByPre(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append("null,");
            return;
        }
        sb.append(root.val + ",");
        serialByPre(root.left,sb);
        serialByPre(root.right,sb);
    }
    
    //使用给定的字符串重建二叉树
    public TreeNode deserialize(String data){
        if(data == null || data.length() == 0)
            return null;
        String[] arr = data.split(",");
        int[] idx = new int[1]; //为了传递的是引用
        
        return reconPre(arr,idx);
    }

    //递归前序建立二叉树
    private TreeNode reconPre(String[] arr,int[] idx) {
        if(idx[0] >= arr.length)
            return null;
        String val = arr[idx[0]];
        if(val.equals("null"))
            return null;
        TreeNode root = new TreeNode(Integer.valueOf(val));
        idx[0]++;
        root.left = reconPre(arr,idx);
        idx[0]++;
        root.right = reconPre(arr,idx);
        return root;
    }
}

或者使用一个存储容器:

public class Codec {
    
    public String serialize(TreeNode root){
        StringBuilder res = new StringBuilder();
        serialByPre(root,res);
        res.deleteCharAt(res.length()-1);//将最后一个,删除
        return res.toString();
    }

    //前序序列化二叉树
    public void serialByPre(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append("null,");
            return;
        }
        sb.append(root.val + ",");
        serialByPre(root.left,sb);
        serialByPre(root.right,sb);
    }
    
    //使用给定的字符串重建二叉树
    public TreeNode deserialize(String data){
        if(data == null || data.length() == 0)
            return null;
        String[] arr = data.split(",");
        Queue<String>queue = new LinkedList<>();
        queue.addAll(Arrays.asList(arr));
        return reconPre(queue);
    }

    //递归前序建立二叉树
    private TreeNode reconPre(Queue<String>queue) {
        if(queue.isEmpty())
            return null;
        String val = queue.poll();
        if(val.equals("null"))
            return null;
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = reconPre(queue);
        root.right = reconPre(queue);
        return root;
    }
}

---

层序序列化和层序反序列化

层序序列化，其实和前序差不多，会层序遍历就差不多，一个逻辑。

public class Codec {
    
    public String serialize(TreeNode root){
        StringBuilder res = serialByLevel(root);
        res.deleteCharAt(res.length()-1);   //将最后一个,删除
        return res.toString();
    }

    public StringBuilder serialByLevel(TreeNode root){
        StringBuilder res = new StringBuilder();
        if(root == null){
            res.append("null,");
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode top = null;
        while(!queue.isEmpty()){
            top = queue.poll();
            if(top != null){
                res.append(top.val + ",");
                queue.add(top.left);
                queue.add(top.right);
            }else {
                res.append("null,");
            }
        }
        return res;
    }

    public TreeNode deserialize(String data){
        String[] strs = data.split(","); 
        int idx = 0;
        TreeNode root = recon(strs[idx++]);
        if(root != null){
            Queue<TreeNode>queue = new LinkedList<>();
            queue.add(root);
            TreeNode top = null;
            while(!queue.isEmpty()){
                top = queue.poll();
                top.left = recon(strs[idx++]);
                top.right = recon(strs[idx++]);
                if(null != top.left)
                    queue.add(top.left);
                if(null != top.right)
                    queue.add(top.right);
            }
        }
        return root;
    }

    private TreeNode recon(String str){
        return str.equals("null") ? null : new TreeNode(Integer.valueOf(str));
    }
}

其中serialByLevel方法也可以这样写:

    public StringBuilder serialByLevel(TreeNode root){
        StringBuilder res = new StringBuilder();
        if(root == null){
            res.append("null,");
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode top = null;
        res.append(root.val + ",");//注意这样写的话 要先添加这个
        while(!queue.isEmpty()){
            top = queue.poll();
            if(top.left != null){
                queue.add(top.left);
                res.append(top.left.val + ",");
            }else
                res.append("null,");
            if(top.right != null){
                queue.add(top.right);
                res.append(top.right.val + ",");
            }else
                res.append("null,");
        }
        return res;
    }