二叉树的序列化与反序列化详解

二叉树的序列化与反序列化详解

引用

CSDN

1.

https://blog.csdn.net/angus52630/article/details/143063166

二叉树的序列化与反序列化是算法面试中常见的问题。序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。本文将介绍如何使用前序、中序、后序以及层序遍历实现二叉树的序列化与反序列化。

问题描述

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

思路

所有二叉树的遍历方式，都可以实现对二叉树的序列化和反序列化，只是在实现细节上有一些不同。

解题方法

对于这棵层序遍历为 [1,2,3,null,null,4,5] 的二叉树

前序遍历

前序遍历是最简单的也是最快的方式。可以直接用逗号分隔所有元素。
编码结果：1,2,#,#,3,4,#,#,5,#,#

public class Codec {
    
    private int i;
    private StringBuilder builder;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        builder = new StringBuilder();
        encode(root);
        return builder.toString();
    }
    private void encode(TreeNode root) {
        if (null == root) {
            builder.append("#,");
            return;
        }
        builder.append(root.val).append(',');
        encode(root.left);
        encode(root.right);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        i = 0;
        return decode(data.toCharArray());
    }
    private TreeNode decode(char[] data) {
        if ('#' == data[i]) {
            i += 2;
            return null;
        }
        TreeNode node = parseNode(data);
        TreeNode left = decode(data);
        TreeNode right = decode(data);
        node.left = left;
        node.right = right;
        return node;
    }
    private TreeNode parseNode(char[] data) {
        int num = 0;
        int sign = 1;
        if ('-' == data[i]) {
            sign = -1;
            i++;
        }
        while (',' != data[i]) {
            num = num * 10 + data[i] - '0';
            i++;
        }
        i++;
        return new TreeNode(num * sign);
    }
}

中序遍历

中序遍历生成的序列里，第一个元素肯定是null，解码时如果先对null进行判断，会直接返回，忽略掉后续序列。一个解决方案是在编码时，在左右子树旁边都加上左括号和右括号。这样解码时先对null进行判断时就会先碰到左括号，不会直接返回。然后在对左右子树递进行归解码前，删除两侧的括号。
编码结果：((#)2(#))1(((#)4(#))3((#)5(#)))

public class Codec {
    // Encodes a tree to a single string.
    private int i = 0;
    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        encode(root, builder);
        return builder.toString();
    }
    private void encode(TreeNode root, StringBuilder builder) {
        if (null == root) {
            builder.append('#');
            return;
        }
        builder.append('(');
        encode(root.left, builder);
        builder.append(')');
        builder.append(root.val);
        builder.append('(');
        encode(root.right, builder);
        builder.append(')');
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        int[] pos = {0};
        return decode(data.toCharArray(), pos);
    } 
    public TreeNode decode(char[] data, int[] pos) {
        if ('#' == data[pos[0]]) {
            pos[0]++;
            return null;
        }
        TreeNode left = parseSubtree(data, pos);
        TreeNode node = new TreeNode(parseInt(data, pos));
        TreeNode right = parseSubtree(data, pos);
        node.left = left;
        node.right = right;
        return node;
    }
    private TreeNode parseSubtree(char[] data, int[] pos) {
        pos[0]++;
        TreeNode node = decode(data, pos);
        pos[0]++;
        return node;
    }
    private int parseInt(char[] data, int[] pos ) {
        int num = 0;
        int sign = 1;
        if ('-' == data[pos[0]]) {
            sign = -1;
            pos[0]++;
        }
        while ('(' != data[pos[0]]) {
            num = num * 10 + data[pos[0]] - '0';
            pos[0]++;
        }
        return num * sign;
    }
}

后序遍历

后序和中序的做法除了调整了递归的顺序外几乎完全一致（后序遍历序列的第一个元素肯定也是null，所以采用了与中序一样的编码方式）。唯一的区别是后序遍历会出现最后一位为数字的情况，在将字符串转成数字时需要对边界进行判断（前序和中序都不用）。
编码结果：((#)(#)2)(((#)(#)4)((#)(#)5)3)1

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        encode(root, builder);
        return builder.toString();
    }
    private void encode(TreeNode root, StringBuilder builder) {
        if (null == root) {
            builder.append('#');
            return;
        }
        builder.append('(');
        encode(root.left, builder);
        builder.append(')');
        builder.append('(');
        encode(root.right, builder);
        builder.append(')');
        builder.append(root.val);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        int[] pos = {0};
        return decode(data.toCharArray(), pos);
    }
    public TreeNode decode(char[] data, int[] pos) {
        if ('#' == data[pos[0]]) {
            pos[0]++;
            return null;
        }
        TreeNode left = parseSubtree(data, pos);
        TreeNode right = parseSubtree(data, pos);
        TreeNode node = new TreeNode(parseInt(data, pos));
        node.left = left;
        node.right = right;
        return node;
    }
    private TreeNode parseSubtree(char[] data, int[] pos) {
        pos[0]++;
        TreeNode node = decode(data, pos);
        pos[0]++;
        return node;
    }
    private int parseInt(char[] data, int[] pos ) {
        int num = 0;
        int sign = 1;
        if ('-' == data[pos[0]]) {
            sign = -1;
            pos[0]++;
        }
        while (pos[0] < data.length && ')' != data[pos[0]]) {
            num = num * 10 + data[pos[0]] - '0';
            pos[0]++;
        }
        return num * sign;
    }
}

层序遍历

层序遍历需要用到队列。而且不仅编码时需要队列，解码时同样需要用到队列。
编码结果：1,2,3,#,#,4,5,#,#,#,#

public class Codec {
    String nul = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<String> result = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        boolean stop = false;
        while (!stop) {
            int n = queue.size();
            stop = true;
            for (int i = 0; i < n; i++) {
                TreeNode cur = queue.removeFirst();
                if (cur == null) {
                    result.add(nul);
                } else {
                    stop = false;
                    result.add(Integer.toString(cur.val));
                    queue.addLast(cur.left);    
                    queue.addLast(cur.right);
                }
            }
        }
        return result.stream().collect(Collectors.joining(","));
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("") || data.equals(nul)) {
            return null;
        }
        String[] strs = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(strs[0]).intValue());
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (!strs[++i].equals(nul)) {
                cur.left = new TreeNode(Integer.valueOf(strs[i]).intValue());
                queue.offer(cur.left);
            }
            if (!strs[++i].equals(nul)) {
                cur.right = new TreeNode(Integer.valueOf(strs[i]).intValue());
                queue.offer(cur.right);
            }
        }
        return root;
    }
}